https://www.zybuluo.com/ysner/note/1221126

单个同余方程

求解形如\(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))\)
这个方程的解就是整个方程组的解。