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;
  }