congruence

If \ (m \mid a-b \), then \ (a \equiv b \pmod m \)

Important formula: \ ({a \bmod b = a-b\lfloor a/b\rfloor} \)

subject

• AcWing202: the luckiest number It's hard (worth doing!)
\Ask how many positive integers composed of at least 8 are multiples of L (\ (L ≤ 2 × 10^9\)​​)
AC code Note: there is a disadvantage of fast power - it may explode long long, which is needed at this time Turtle speed ride

• AcWing97: Sumdiv Canon
\Find the sum of all divisors of \ (A^B \) mod 9901
AC code

• Calculator Template (worth doing!)

$$general idea$$ ask \ (a^b\bmod p \), \ (ax\equiv b\pmod p \), \ (a^x\equiv b\pmod p \)

AC code

• Desert island Savage Finding congruence without solution

$$main idea$$ find the minimum M so that for any i,j, the following congruence equation has no solution:





$$AC code$$

$$question$$ in solving the linear congruence equation:

int getK(Being o1, Being o2, int m){
int a=Mod(o1.P-o2.P, m), b=o2.C-o1.C, m;   //It's strange here (try to swap the two subtraction operands, or add or remove the Mod of a or b...) It seems to be feasible in mathematics, but the algorithm can't solve it
int x, y, d=exgcd(a, m, x, y);
if(b%d!=0) return -1;
return Mod(x*b/d, m/d);
}


nature

• Multiplicity: if \ (a\equiv b\pmod m \) and \ (c\equiv d\pmod m \), there is \ (ac\equiv bd\pmod m \)
• Isomorphism: if \ (a\equiv b\pmod m \), then \ (a^n\equiv b^n\pmod m \)
• If \ (a\bmod p=x,\ a\bmod q=x \) and p, q are coprime, then \ (a\bmod (pq)=x \)
• Does not satisfy the identity division

Algorithms and theorems

• Fermat's theorem: if p is a prime number, there is \ (a^p \equiv a\pmod p \) for any integer a
(Fermat's small theorem is a special case of Euler's theorem)

• Euler's theorem: if positive integers a and N are coprime, then \ (a^{\varphi(n)} \equiv 1\pmod n \)
Inference (can be used to reduce the scale of the index to a range that is easy to calculate):

1. If the positive integers a and N are coprime, there is \ (a^b \equiv a^{b\bmod \varphi(n)}\pmod n \) for any positive integer b
2. When a and N are not necessarily coprime, and \ (b > \ varphi (n) \) has \ (a^b \equiv a^{b \bmod \varphi(n)+\varphi(n)}\pmod n \)
3. If positive integers a and B are coprime, the minimum positive integer satisfying \ (a^x \equiv 1\pmod n \) \ (x_0 \) is the divisor of \ (\ varphi(n) \)
• Bezout theorem: for any integer a,b, there is a pair of integers x,y, satisfying \ (ax+by=\gcd(a,b) \)
Given that a,b, X and y satisfy the above formula, it can be used extended euclidean algorithm :

• Multiplicative inverse: if integers B and m are coprime and \ (b\mid a \), there is an integer x such that \ (a/b \equiv a × x\pmod m \), which is called the multiplicative inverse of B module M and is recorded as \ (b^{-1}\pmod m \)

• $$b × b^{-1} \equiv 1\pmod m$$ the congruence equation is the main formula for solving the multiplicative inverse
• When m is prime, then \ (b × b^{m-2} \equiv 1\pmod m\)
• If B and m are not coprime, then \ (bx \equiv 1\pmod m \) has no integer solution, that is, there is no multiplicative inverse
• Linear congruence equation \ (ax \equiv b\pmod m \) this equation is equivalent to \ (ax+my=b \)

• Solvable if and only if \ (\ gcd(a,m)\mid b \)
• solve An algorithm for finding the Euclidean solution of (CD \ \ Gu, x = \\\\\\\\\\ × b/ \gcd(a, m) \) is a solution of the original congruence equation
• Solution (CD \ {\ gquim})

code

• ll exgcd(ll a, ll b, ll &x, ll &y){
if(!b){ x=1, y=0; return a; }
ll d=exgcd(b, a%b, x, y);
ll t=x; x=y; y=t-y*(a/b);  // Key points (this formula comes from the proof of Bezout theorem)
return d;
}

• Solve \ (ax\equiv b\pmod p \)

inline ll Mod(ll a, ll b){ return (a%b+b)%b; }	// a is the smallest positive integer with modulus b

ll solve(ll a, ll b, ll p){
ll x, y, d=exgcd(a, p, x, y);
if(b%d!=0) return -1;	// unsolvable
return Mod(x*b/d, abs(p/d));	// Note that the modulus here is p/d, not P,
}


In some topics, such as Desert island Savage , d may be negative, so abs is needed
In addition, don't mod (a, P) or mod (B, P) at the beginning I don't know the reason. The question of "desert island savage" will inexplicably WA

• Solving Linear Congruence Equations



x\equiv a_1\pmod {m_1} \
x\equiv a_2\pmod {m_2} \
... \
x\equiv a_n\pmod {m_n}
\end{cases}



  cpp
ll res=0;
REP(i, 1, n) M*=m[i];
REP(i, 1, n){
ll Mi=M/m[i], x, y;
exgcd(Mi, m[i], x, y);
res=Mod(res+A[i]*Mi*x%M, M);	// The multiplication of three numbers here may explode long long, which can be multiplied at turtle speed
}
printf("%lld\n", Mod(res, M);


1. When \ (m \) does not guarantee mutual prime, it can be obtained by extended Euclidean algorithm + mathematical induction recursion Examples
ll solve(){
ll M=1, o=0;
REP(i, 1, n){
if(!(M%mo[i]) && x0%mo[i]==A[i]) continue;  // accelerate
ll x, y, b=Mod(A[i]-o, m[i]);
ll d=exgcd(M, m[i], x, y);
if(b%d!=0) return -1;
x=smul(x, b/d, m[i]/d);	// Multiplication is an abomination because it explodes easily

ll t=M; M=M/d*m[i];	// M = lcm{m}
o=Mod(o+smul(x, t, M), M);	// Turtle speed ride
}
return o;
}

• Minimum positive integer solution of \ (a^x\equiv b\pmod p \) for solving high-order congruence equation (Baby Setp, Giant Setp algorithm)

map<ll, int> h;
ll solve_3(ll a, ll b, ll p){
h.clear(); a%=p, b%=p;  // Mold it first This sentence can't be saved!

ll sp=ceil(sqrt(1.0*p));
FOR(j, 0, sp){
ll t=b*qpow(a, j, p)%p;
h[t]=j;
}

a=qpow(a, sp, p);
if(a==0) return b==0 ?1 :-1;    // Cannot return 0!
REP(i, 0, sp){
ll t=qpow(a, i, p);
int j=(h.count(t) ?h[t] :-1);
if(j>=0 && i*sp-j>=0) return i*sp-j;
}
return -1;
}


Keywords: Math

Added by DontheCat on Tue, 08 Mar 2022 03:22:18 +0200