同余

若 \(m \mid a-b\) 则 \(a \equiv b \pmod m\)

重要公式: \({a \bmod b = a-b\lfloor a/b\rfloor}\)

题目

• AcWing202: 最幸运的数字典 难 　(值得一做!)
  \(大意\) 问至少多少个 8 连在一起组成的正整数是 L 的倍数 (\(L≤2×10^9\)??)
  AC代码 注意: 快速幂有个缺点 - 可能会爆 long long, 此时需用龟速乘

• AcWing97: Sumdiv 典
  \(大意\) 求 \(A^B\)的所有约数之和 mod 9901
  Q: 无乘法逆元时, 如何计算分式之模?
  A: 部分题目有特殊条件. 比如此题, 当\(P\mid p_i-1\)时, 即有\(p_i\equiv 1\pmod P\)
  AC代码

• 计算器 模板　(值得一做!)
  \(大意\) 求 \(a^b\bmod p\), 　\(ax\equiv b\pmod p\)?, 　\(a^x\equiv b\pmod p\)

  AC代码

• 荒岛野人 求同余式无解 典

  简析

  \(大意\) 求最小的 M 使得对于任意的 i,j 使得如下同余方程无解：

  \[C_i+xP_i\equiv C_j+xP_j\pmod M\quad (x>\min(L_i,L_j)) \]

  \(简析\) 暴力枚举 m, 并对 n² 个同余式进行求解 检验.
  \(AC代码\)
  \(疑问\) 在该题求解线性同余方程中:

  int getK(Being o1, Being o2, int m){
  	int a=Mod(o1.P-o2.P, m), b=o2.C-o1.C, m;   //这里很奇怪.. (试着把 俩减操作数对调, 或者把a或b的Mod加上或去掉..) 好像在数学中是可行的, 但算法求解就不行了
  	int x, y, d=exgcd(a, m, x, y);
  	if(b%d!=0) return -1;
  	return Mod(x*b/d, m/d);
  }
  

性质

• 同乘性: 若 \(a\equiv b\pmod m\) 且 \(c\equiv d\pmod m\), 则有 \(ac\equiv bd\pmod m\)
• 同幂性: 若\(a\equiv b\pmod m\) 则 \(a^n\equiv b^n\pmod m\)
• 若 \(a\bmod p=x,\ a\bmod q=x\) 且 p, q 互质, 则 \(a\bmod (pq)=x\)
• 不满足 同除性.

算法与定理

• 费马小定理: 若p为质数, 则 对于任意整数a, 有\(a^p \equiv a\pmod p\)
  (费马小定理是欧拉定理的一个特例)

• 欧拉定理: 若正整数 a,n 互质, 则 \(a^{\varphi(n)} \equiv 1\pmod n\)?
  推论 (可用于将 指数的规模缩小 到容易计算的范围):

  1. 若正整数 a,n 互质, 则对于任意正整数 b, 有 \(a^b \equiv a^{b\bmod \varphi(n)}\pmod n\)
  2. 当 a,n 不一定互质, 且 \(b>\varphi(n)\)有 \(a^b \equiv a^{b \bmod \varphi(n)+\varphi(n)}\pmod n\)
  3. 若正整数 a,b 互质, 则满足 \(a^x \equiv 1\pmod n\)的 最小正整数 \(x_0\) 是 \(\varphi(n)\)的约数

• Bezout定理: 对于任意整数 a,b, 存在一对整数 x,y, 满足 \(ax+by=\gcd(a,b)\)
  已知 a,b, 求解 x,y 满足上式, 可使用 扩展欧几里得算法:

• 乘法逆元: 若整数 b,m 互质, 且 \(b\mid a\), 则存在一个整数 x, 使得 \(a/b \equiv a×x\pmod m\), 称 x 为 b模m的乘法逆元, 记为 \(b^{-1}\pmod m\)

  • \(b×b^{-1} \equiv 1\pmod m\) 该同余方程为求解乘法逆元的主要式子
  • 当m为质数, 则 \(b×b^{m-2} \equiv 1\pmod m\)
  • 若 b,m 不互质, 则 \(bx \equiv 1\pmod m\) 无整数解, 即不存在乘法逆元

• 线性同余方程 \(ax \equiv b\pmod m\) 该方程等价于 \(ax+my=b\)

  • 有解　当且仅当 \(\gcd(a,m)\mid b\)
  • 求解　欧几里得算法求 \(ax+my=\gcd(a, m)\) 的一个解 \(x_0\), \(x=x_0×b/ \gcd(a, m)\)? 即为原同余方程的一个解.
  • 通解　\(x'\equiv x\pmod {\frac{m}{gcd(a, m)}}\)

代码

• 荒岛野人, d解出来可能为负数, 此时就要abs.
  另外, 最开始时不要 Mod(a, p), Mod(b, p). 原因我也不知道, 在"荒岛野人"那题就会莫名其妙地WA.

• 求解 线性同余方程组

  \[ \begin{cases} x\equiv a_1\pmod {m_1} \\ x\equiv a_2\pmod {m_2} \\ ... \\ x\equiv a_n\pmod {m_n} \end{cases} \]
  1. 当 \(m\) 两两互质时, 可以用 中国剩余定理

     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);	// 这里的三数相乘可能会爆 long long, 可用龟速乘
     }
     printf("%lld\n", Mod(res, M);
     

  2. 当 \(m\) 不保证两两互质时, 可以用 扩展欧几里得算法+数学归纳递推求出　例题

     ll solve(){
         ll M=1, o=0;
         REP(i, 1, n){
             if(!(M%mo[i]) && x0%mo[i]==A[i]) continue;  // 加速
             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);	// 乘法是个可恶的家伙, 因为它很容易爆.
     
             ll t=M; M=M/d*m[i];	// M = lcm{m}
             o=Mod(o+smul(x, t, M), M);	// 龟速乘
         }
         return o;
     }
     

• 求解 高次同余方程 之 \(a^x\equiv b\pmod p\) 的最小正整数解 (Baby Setp, Giant Setp 算法)

  map h;
  ll solve_3(ll a, ll b, ll p){
  h.clear(); a%=p, b%=p;  // 先模一遍. 这句话不能省!
  
  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;    // 不能返回 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;
  }