中国剩余定理
模板代码：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e5+10;
#define int ll
int n,m[300],r[300];
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
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);
ans=(ans+r[i]*c*x%M)%M;
}
return (ans%M+M)%M;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>m[i]>>r[i];
}
cout<<crt(m,r);
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while (t--){
solve();
}
return 0;
}原文地址：https://blog.csdn.net/qq_73631501/article/details/140280135
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！