关于同余方程解法

数论

单个同余方程

求解形如$Ax\equiv B(mod\ M)$的最小正整数解。

il void exgcd(re ll A,re ll B,re ll &D,re ll &x,re ll &y)
{
  if(!B) x=1,y=0,D=A;
  else exgcd(B,A%B,D,y,x,c),y-=(A/B)*x;
}
il void solve2()
{
  re ll A=atk[1],B=a[1],M=p[1],D,x,y,ysn,zsy;
  exgcd(A,M,D,x,y);//D=gcd(A,M)
  if(B%D) {puts("-1");return;}
  x=x*(B/D)%(M/D);
  printf("%lld\n",x);
}

解释一下：
$Ax\equiv B(mod\ M)$
$Ax=My+B$
$Ax+My=B$(正负号不重要）
于是就是解$Ax+My=B$这个不定方程。

根据斐蜀定理：$ax+by=c=k*gcd(a,b)(k\in N^{*})$
所以必须$gcd(A,M)|B$，否则无解。
设$a>b$。
当$b=0,gcd(a,b)=a$,所以此时$x=1,y=0$
当$a>b>0$时，设$ax_1+by_1=gcd(a,b),bx_2+(a\ mod\ b)y_2=gcd(b,a\ mod\ b)$
根据欧几里德原理，则
$ax_1+by_1=bx_2+(a\ mod\ b)y_2$
即$ax_1+by_1=bx_2+(a-(a/b)*b)y_2=ay_2+bx_2-(a/b)*by_2$
对应得$x_1=y_2,y_1=x_2-(a/b)*y_2$

于是我们就可以一边求$gcd$一边解这个方程。
当然，注意到跑了$exgcd$后解出来的是$ax+by=gcd(a,b)$
解同时乘上$c/gcd(a,b)$即可。
注意到$x,y$的解不止一个，$x+=b/gcd(a,b),y-=a/gcd(a,b)$后总是合法。（因为加减的都是$ab/gcd(a,b)=lcm(a,b)$)。
为了求最小正整数值，我们模这个值即可。

如果要把最后一步套路化，就是$D=gcd(A,B),x=z*(B/D)\%(M/D)$

模数互质的同余方程组

用中国剩余定理（孙子定理）解决。
讲这玩意儿需要栗子。
在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以$3$余$2$），五五数之剩三（除以$5$余$3$），七七数之剩二（除以$7$余$2$），问物几何？”

首先，我们假设$n_1$是满足除以$3$余$2$的一个数。同样，我们假设$n_2$是满足除以$5$余$3$的一个数，$n_3$是满足除以$7$余$2$的一个数。

现在把$n_1+n_2+n_3$作为该问题最终解。
则依“两数相加则模数相加”：

• $n_1$除以$3$余$2$，且是$5$和$7$的公倍数。
• $n_2$除以$5$余$3$，且是$3$和$7$的公倍数。
• $n_3$除以$7$余$2$，且是$3$和$5$的公倍数。

所以，孙子问题解法的本质是对每一个方程，从其它所有模数公倍数中找出符合该方程的解，最终解就是这些解相加。

在求$n_1$，$n_2$，$n_3$时又用了一个小技巧，以$n_1$为例，并非从$5$和$7$的公倍数中直接找一个除以$3$余$2$的数，而是先找一个除以$3$余$1$的数，再乘以$2$。也就是找解时先求出公倍数模数下的逆元，再用逆元去乘余数。

找逆元和解单个同余方程一样。

模数不互质的同余方程

用拓展中国剩余定理解决。
还是栗子。
有一同余方程组：(注意到$x$没有系数）
$x\equiv b_1(mod\ m_1)$
$x\equiv b_2(mod\ m_2)$
则$x=k_1m_1+b_1=k_2m_2+b_2$
发现右边两个表达式相等可以看做一个方程$m_1k_1+m_2k_2=b_2-b_1$
显然可以拓欧求解$k_1,k_2$。

又由斐蜀定理可知，$m_1x+m_2y=gcd(m_1,m_2)$
所以$k_1=\frac{b_2-b_1}{gcd(m_1,m_2)}$
将$k_1$代入$x=b_1+k_1m_1$即可得出特解$x'$
如果解出特解$x'$，则$x=x'+k*lcm(m_1,m_2)$。
则$x\equiv x'(mod\ lcm(m_1,m_2))$
这个方程的解就是整个方程组的解。