中国剩余定理(CRT)
中国剩余定理可以用来求解下面的线性同余方程组 做法如下:
- 计算所有的模数的积为M
- 计算第i个方程的
- 求再模下的逆元
题目链接: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;
}