中国剩余定理及多项式模非素数学习笔记 | Bill Yang's Blog

中国剩余定理及多项式模非素数学习笔记

中国剩余定理解决线性同余方程组的方法,在数论中占据重要地位。

中国剩余定理(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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
LL Exgcd(LL a,LL b,LL& x,LL& y) {
if(b==0) {
x=1;
y=0;
return a;
}
LL ans=Exgcd(b,a%b,x,y),tmp=x;
x=y;
y=tmp-a/b*y;
return ans;
}
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],x0,y0;
Exgcd(Mi,b[i],x0,y0);
ans=(ans+Mi*x0*a[i])%M;
}
return (ans+M)%M;
}
LL n,a[15],b[15];
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
b[i]=Get_Int();
}
printf("%lld\n",CRT(n,b,a));
return 0;
}

代码(当模数均为质数)

此时我们可以直接使用快速幂求逆元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
LL 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;
}

姥爷们赏瓶冰阔落吧~
0%