跳到主要内容

中国剩余定理(CRT)

中国剩余定理可以用来求解下面的线性同余方程组 {xr1(modm1)xr2(modm2)xrn(modmn)\left\{\begin{array}{c} x \equiv r_{1}\left(\bmod m_{1}\right) \\ x \equiv r_{2}\left(\bmod m_{2}\right) \\ \vdots \\ x \equiv r_{n}\left(\bmod m_{n}\right) \end{array}\right. 其中模数m1,m2,,mn为两两互质的整数,x的最小非负整数解。其中模数 m_{1}, m_{2}, \cdots, m_{n} 为两两互质的整数, 求 x 的最小非负整数解。 做法如下:

  1. 计算所有的模数的积为M
  2. 计算第i个方程的ci=Mmic_i=\frac{M}{m_i}
  3. cic_i再模mim_i下的逆元ci1c_i^{-1}
  4. x=i=1nricici1(modM)x=\sum_{i=1}^{n}{r_ic_ic_i^{-1}}(\bmod M)

题目链接:https://www.luogu.com.cn/problem/P1495

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 20;

int n;
LL m[N],r[N];


LL exgcd(LL a,LL b,LL &x,LL &y){
if (b==0){
x=1,y=0;
return a;
}
LL x1,y1,d;
d= exgcd(b,a%b,x1,y1);
x=y1,y=x1-a/b*y1;
return d;
}

LL CRT(LL m[],LL r[]){
LL M=1,ans=0;
for(int i=1;i<=n;i++) M*=m[i];
for(int i=1;i<=n;i++){
LL c=M/m[i],x,y;
exgcd(c,m[i],x,y);
//x为c的乘法逆元
ans=(ans+r[i]*c*x%M)%M;
}
return (ans%M+M)%M;//这样是为了求最小非负整数解
}

int main() {
IOS;
#ifndef ONLINE_JUDGE
freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
cin>>n;
for(int i=1;i<=n;i++) cin>>m[i]>>r[i];
pr(CRT(m,r))

return 0;
}