congruence
If \ (m \mid ab \), then \ (a \equiv b \pmod m \)
Important formula: \ ({a \bmod b = ab\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 \)

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:
\[\]\[ \]\(question \) in solving the linear congruence equation:
int getK(Being o1, Being o2, int m){ int a=Mod(o1.Po2.P, m), b=o2.Co1.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): 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
 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 \)
 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^{m2} \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=ty*(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); ```
 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; }
 When \ (m \) does not guarantee mutual prime, it can be obtained by extended Euclidean algorithm + mathematical induction recursion Examples

Minimum positive integer solution of \ (a^x\equiv b\pmod p \) for solving highorder 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*spj>=0) return i*spj; } return 1; }