中国剩余定理（CRT）

引出

        在《孙子算经》中有这样一个问题：

        “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”

也就是说有如下的方程组：

       求该方程组的解

设为最小整数解：

则   

令   ，且

通过取模得0的几个式子可以得到其最小公倍数

上述均可化为   的形式求逆元

中国剩余定理

用于求解以下式子，其中  两两互质：

过程：

计算所有  的乘积 B

对于第i个式子：

• 前i-1个式子的解为ans
• 计算  以及  在模  意义下的逆元 
• 前i个式子的解为  

最终解为  

证明：

对于所有的  ，必定有    个  为  的因子，即  

反过来说对于  只有  不为其倍数

根据  ，则有  

在  时  皆为  的倍数， 所以  

  是  模  意义下的逆元，化简 ，可证得同余方程组解的正确性

一般需要用到龟速乘来确保不会溢出：

long long CRT()
{
	long long ans = 0;
	long long m = 1;
	for(int i = 1;i <= n;i++)
	{
		m *= b[i];
	}
	for(int i = 1;i <= n;i++)
	{
		long long mi = m / b[i];
		exgcd(mi,b[i]);
		x = (x % b[i] + b[i]) % b[i];
		ans = (ans + slow_mul(mi,x*a[i],m) % m + m) % m;
	}
	return (ans % m + m) % m;
}

扩展中国剩余定理

同样对于以下式子，其中  不保证互质：

过程：

• 对于前i-1个式子，假设已求得答案，对于第1个式子有 
• 令  ，则前i-1个式子通解为 
• 第i个方程的解既要满足第i个方程也要满足前i-1个方程，则 
• 将该式代入第i个方程求解 
• 转化一下式子：  ，可以用exgcd求解k
• 将解得的k带回  可得到前i个方程的解

重复该步骤即可求得n组方程的解x

long long EXCRT()
{
	long long res = a[1];
	long long m = b[1];
	for(int i = 2;i <= n;i++)
	{
		long long A = m;
		long long B = b[i];
		long long C = (a[i] - res + B) % B;
		exgcd(A,B);
		x = slow_mul(x,C/__gcd(A,B),B);
		res += x*m;
		m = lcm(m,B);
		res = (res%m + m) % m;
	}
	return res;
}

注意有些题目可能有无解的情况，判断exgcd有无解即可