中国剩余定理解决线性同余方程组的方法，在数论中占据重要地位。
中国剩余定理（CRT）
若$m_1,m_2,\ldots,m_k$为互素正整数，则同余方程组：
有模$M=m_1\times m_2\times\cdots \times m_k$的唯一解。
解为：$(M_1M_1’a_1+M_2M_2’a_2+…+M_kM_k’a_k)\bmod M$
其中$M_i=\frac{M}{m_i}$,$M_i’$是$M_i$模$m_i$的乘法逆元。
因为模数必须互素，因此CRT的应用受到限制，如果模数不互素可以考虑拆成互素或使用扩展欧几里得求解线性同余方程组（即扩展中国剩余定理）
证明
略，可以参考百度资料
应用
多项式模非素数
有许多多项式模$p$的题目受到$p$是素数的限制。
如组合数$C_n^m\bmod p$我们有以下六种解法（于2018/1/6更新）：
$1\le n,m\le1000$
利用杨辉三角递推计算组合数。
$1\le n,m\le10^7$,$p$是素数
预处理阶乘，线性处理逆元计算组合数。
$1\le n,m\le10^{18},p\le10^6$,$p$是素数
利用Lucas定理分解后计算。
$1\le n,m\le10^6,p\le10^5$,$p$可能是合数
建立素因子表，枚举每个素因子，统计$n!,m!,(n-m)!$中含有素因子的个数，然后对进行快速幂。
$1\le n,m\le10^{18},p\le10^{18}$,$p$可能是合数,$p$分解质因数后的$p’\le10^6$，且$p’$幂次均为$1$。
分解素数依次使用Lucas定理计算，再利用CRT合并组合数。
具体方案是：
将$p$分解成若干$p’$相乘，存入$p’[]$，使用Lucas定理计算$C_n^m\bmod p’$，并存到$a[]$中。
利用CRT计算$a[],p’[]$的解，因为CRT有唯一解，因此可以得到$C_n^m\bmod p$。
当然这要求分解出的$p’$比较小且分解的$p’$个数不多，一般这类题$p’$都是给定值。
$1\le n,m\le10^{18},p\le10^{18}$,$p$是任意数,$p$分解质因数后的$p’\le10^6$。
使用扩展Lucas定理分解素数计算，再用CRT合并组合数。
CRT合并方法与上一种解法类似。
当然除了组合数CRT还可以用来计算其他的多项式模非素数的问题。
代码（曹冲养猪）
1 |
|
代码（当模数均为质数）
此时我们可以直接使用快速幂求逆元。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21LL Quick_Pow(LL a,LL b,LL mod) {
LL ans=1;
while(b) {
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
LL inv(LL a,LL mod) {
return Quick_Pow(a,mod-2,mod);
}
LL CRT(LL n,LL* a,LL* b) {
LL M=1,ans=0;
for(int i=1; i<=n; i++)M*=b[i];
for(int i=1; i<=n; i++) {
LL Mi=M/b[i];
ans=(ans+Mi*inv(Mi,b[i])*a[i])%M;
}
return (ans+M)%M;
}
扩展中国剩余定理
由于中国剩余定理只能在模数互质的情况下使用，但多数情况模数是不互质的，这个时候我们要考虑使用扩展欧几里得算法合并同余方程。
假设我们要合并：
即：
那么有：
即：
可以用扩展欧几里得算法求出$x_1$的最小正整数解。
代入第一个方程得：
而$x’$与最终答案的$x$的关系是模$lcm(m_1,m_2)$成立，即：
于是可以合并$n-1$次，得到最终的解。
代码
1 | void Exgcd(LL a,LL b,LL &d,LL &x,LL &y) { |
