中国剩余定理 CRT

问题：有$n$个这样形式的方程组：$x\equiv c_i\mod m_i$。求通解和最小解。

一般的做法

考虑如何合并

$$\begin{cases} x \equiv c_1\mod m_1\\ x \equiv c_2 \mod m_2\\ \end{cases}$$

我们设

$$x=c_1+k_1m_1 = c_2 + k_2m_2$$

即

$$k_1m_1-k_2m_2 = c_2 - c_1$$

用扩展欧几里得解出$k_1$即可。

void CRT(ll *c,ll *m,int n)
{
	for(int i=1;i<n;++i)
	{
		ll x,y,g=exgcd(m[0],m[i],x,y);
		ll tmp=m[i]/g,M=lcm(m[0],m[i]);
		x=(Mul(x,(c[i]-c[0])/g,tmp)+tmp)%tmp;
		c[0]=(c[0]+Mul(x,m[0],M))%M,m[0]=M;
	}
}

注意，扩展欧几里得通解的最小间隔是$m_2\over gcd(m_1,m_2)$。

---

$m_i$两两互质或者可以预处理欧拉函数

以下两种做法，仅适用于$m_i$两两互质或者可以预处理欧拉函数的情况：

一个比较通用的方法

考虑将两个方程$x\equiv b_1\mod m_1$与$x\equiv b_2 \mod m_2$合并。

由欧拉定理得

$$m_2^{\varphi (m_1)}\equiv 1 \ mod \ m_1\\ \therefore b_1m_2^{\varphi(m_1)}\equiv b_1\ mod\ m_1\\ \because m_1\equiv 0 \ mod \ m_1\\ \therefore b_2m_1^{\varphi(m_2)}\equiv 0\ mod \ m_1\\ \therefore b_1m_2^{\varphi(m_1)}+b_2m_1^{\varphi(m_2)}\equiv b_1\ mod \ m_1$$

同理可证

$$b_1m_2^{\varphi(m_1)}+b_2m_1^{\varphi(m_2)}\equiv b_2\ mod \ m_2$$

发现这两个方程长的像原来的方程组

得到：

$$x\equiv b_1m_2^{\varphi(m_1)}+b_2m_1^{\varphi(m_2)}\ mod \ ( lcm(m_1,m_2))$$

将所有的方程组依次合并即可。

一个只适用于$\prod m_i$不会超出unsigned long long 范围的方法

我们如果把所有的方程组合并完，可以得到：

$$M=\prod m_i\\ x= \sum c_i\times ({M\over m_i})^{\varphi(m_i)}$$

模数自然是$lcm(m_1,m_2,\dots m_n)$

这样合并的话，考虑将合并过后的结果带回原来的方程组，对于$c_i$的这一项，当模数是$m_i$时，$({M\over m_i})^{\varphi(m_i)}\equiv 1$；当模数不为$m_i$的时候$({M\over m_i})^{\varphi(m_i)}\equiv 0$。那么这个通解的正确性也是显然的了。

Tips

其实求$x^{\varphi(m_i)}$的过程相当于求$x$与$x$在模$m_i$意义下的逆元的乘积，所以我们可以把这个计算过程换成扩展欧几里得。但是，这样做的前提是，$m_i$两两互质。

---

为什么模数是$lcm(m_1,m_2\cdots m_n)$

证明通解一定是$x\equiv c\mod lcm(m_1,m_2\cdots m_n)$的形式，本质就是要证明：相邻的两个解之间的差恰好为$lcm(m_1,m_2\cdots m_n)$。

考虑只有两个模数的情况（其他可以类似推出），若$x\equiv c_1\mod m_1$，那么$\cdots c_1-m_1,c_1,c_1+m_1,c_1+2m_1\cdots $对第一个方程来说，都是可行的$x$。因此对第一个方程可行的$x$恰好每$m_1$个数中就有一个，即解之间的间隔为$m_1$。而第二个方程的解的间隔是$m_2$。假若合并得到的是$x\equiv c$，那么$c$一定既是第一个方程的可行解，又是第二个方程的可行解。假设另一个解是$x’$，那么一定有$m_1|x-x’$并且$m_2|x-x’$，也就是说解的间隔是$m_1,m_2$的公倍数，所以解之间的最小间隔就是$lcm(m_1,m_2)$。