The article directories

  • congruence
    • Unary linear congruence equation
  • inverse
    • Modulus of inverse element and division
  • sample
    • HDU-5976

congruence

Two integers a a a a and b b b and the module m m m, if a a a% m=b m=b m=b% m m m, a a a and b b b are congruent to m m m. Congruence can also be understood as a – b a – a – b b is twice as large as the m m m: m ∣ (a – b) m | m (a – b) ∣ (a – b), such as 6 ∣ (23-11) 6 | (23-11) 6 ∣ (23-11), 11 to 23 and mode 6 congruence. Congruence notation is calculated as A ≡b(M od A ≡b(mod A ≡b(mod m) m) m).

Unary linear congruence equation

A x≡b(M od ax≡b(mod ax≡b(mod m) m) m), solve for x. A x−b ax-b ax−b is a multiple of m, m, m. Let the multiple be y, y, y, then ax−my=b ax-my=b ax−my=b. Then we can use extended Euclid to solve for x, x, x. However, if gcd(a,m) ≠ b GCD (a,m)\neq b GCD (a,m)=b, the extended Euclidean solution cannot be used, and the following inverse element should be combined.

inverse

Given a A a a and m m m, solve ax≡1(M od ax≡1(mod ax≡1(mod m) m) m), i.e. the remainder of ax ax ax divided by m m m is 1 1 1. So one of the solutions to this equation x x x is called the inverse of a a a module m m m, and notice that there are many of these x, x, x, they are called the inverse. Extended Euclidean can refer to the previous article extended Euclidean inverse element:

ll inv(ll a, ll m){
	ll x, y;
	ll gcd = extend_gcd(a, m, x, y);
	return	(x % m + m) % m;// Pay attention to negative numbers
}
Copy the code

Recursive inverse element:

inv[1] = 1;
for (i = 2; i < n; i++)
    inv[i] = inv[mod % i] * (mod - mod / i) % mod;
Copy the code

Modulus of inverse element and division

An important function of the inverse element is to find the modulus of division. First let’s look at the modulus operation:

  • Add: (a + b) (a + b) (a + b) % m = (a m = (a m = (m + a % m + m + b b b % m) m) m) % m m m
  • Reduction: (a – b) (a – b) (a – b) % m = (a m = (a m = (a % m – m – m – b b b % m) m) m) % m m m
  • X (a ∗ b) : (a) * b (a ∗ b) % m = (a m = (a m = (a % m ∗ b m * m ∗ b % m b) m) m) % m m m
  • In addition to: (a/b) (a/b) (a/b) % m indicates (a m \ neq  (a m = (a % m m m/m/b/b b %) m) m) % m m m

Obviously, multiplication is true for addition and subtraction, but division is not satisfied, such as (100/50)%20=2, and (100%20)/(50%20)=0. And then you can use the inverse. Let the inverse of b b be k, k, k, then: a b \frac{a}{b} ba% m = ( a b m=(\frac{a}{b} m=(ba% m ) ( b k m)(bk m)(bk% m ) = ( a b b k ) m)=(\frac{a}{b}bk) M) = (babk) % m = a k m = ak is ak % m m m m = (a/b) (a/b) (a/b) % m = (a k) m = (ak) m = (ak) % m m m

sample

HDU-5976

HDU-5976 Detachment

Problem Description In a highly developed alien society, the habitats are almost infinite dimensional space. In the history of this planet,there is an old puzzle. You have a Line segment with X units’ length representing one dimension.The line segment can be split into a number of small line Segments: a1, a2,… (x = a1 + a2 +…). assigned to different dimensions. And then, the multidimensional space has been established. Now there are two requirements for this space: 3. Two different small line segments cannot be equal (AI ≠ AJ when I ≠ J). 4 Large as possible (s= A1 * a2…) Note that it allows to keep one dimension. the number of ai can be only one. Now can you solve this question and find the maximum size of the space? (For the final number is too large,your answer will be modulo 10^9+7) Input The first line is an integer T,meaning the Each line contains one integer x. 1≤T≤10^6, 1≤x≤10^9 Output Maximum s you can get modulo 10^9+7. Note that we want to be the greatest product before modulo 10^9+7. Sample Input 1 4 Sample Output 4

Divide a number into several numbers and find the largest product. The first conclusion is: if a number n is divided into m numbers to maximize its product, then it is divided into M n/ M; If nm is not divisible, it is split into a continuous natural number (starting at 2 and amortizing the rest); If you don’t limit m, you split it into 3 at most and 2 at the rest. The numbers are not the same, so they are divided into consecutive numbers starting from 2, and then the preprocessing + inverse modulo can be seen in the code.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 10;
const int mod = 1e9 + 7;
ll sum[maxn];
void init(a){
	sum[0] = sum[1] = 1;
	for (int i = 2; i < maxn; i++)
		sum[i] = i * sum[i - 1] % mod;
}
ll extend_gcd(ll a, ll b, ll& x, ll& y){
	if (b == 0){
		x = 1; y = 0;
		return a;
	}
	ll gcd = extend_gcd(b, a % b, y, x);
	y -= x * (a / b);
	return gcd;
}
ll inv(ll a, ll m){
	ll x, y;
	ll gcd = extend_gcd(a, m, x, y);
	return	x = (x % mod + mod) % mod;
}
int main(a){
	ll t, s;
	init(a);scanf("%lld", &t);
	while (t--){
		scanf("%lld", &s);
		if (s <= 4) {
			printf("%d\n", s);
			continue;
		}
		ll n = (ll)((- 1 + sqrt(8 * s + 9.0)) / 2 + 0.5);
		while ((2 + n) * (n - 1) / 2 > s) n--;
		int tmp = s - (2 + n) * (n - 1) / 2;/ / difference,
		ll mi = 2 + tmp / (n - 1);// The minimum value in the multiplication
		ll mx = tmp % (n - 1)? n + tmp / (n -1) + 1 : n + tmp / (n - 1);// The maximum value in the multiplication
		ll temp = 2 + tmp / (n - 1) + n - 1 - tmp % (n - 1);// The broken number in the multiplication
		ll ans = inv(sum[mi - 1], mod) * sum[mx] % mod;
		if (temp <= mx)
			ans = (ans * inv(temp, mod)) % mod;
		printf("%lld\n", ans);	
	}
	return 0;
}
Copy the code

Original is not easy, please do not reprint (this is not rich visits add insult to injury) blogger home page: blog.csdn.net/qq_45034708 If the article is helpful to you, remember to focus on the likes collection ❤