#C231109C. 中国剩余定理
标签（Label）
数学
exgcd
模板
网址（Website）
题目详情 - 【NOIP模板】中国剩余定理 - 曹冲养猪 - Super
题解 - 【NOIP模板】中国剩余定理 - 曹冲养猪 - Super
题解（Solution）
$\qquad$中国剩余定理就不用讲了，题解已经讲得够清晰了，只是这几天一直考数学，看到这道题比较妙，有多种解法，于是记录下来。
$\qquad$有问题看 OI-Wiki 就好了。
代码（Code）
中国剩余定理
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1012345;
inline int exgcd(int a,int b,int &x,int &y){
if(!b) return x=1,y=0,a;
int d=exgcd(b,a%b,y,x);
y-=a/b*x;return d;
}
int a[N],b[N],m[N],t[N];
int sum=1,ans,n,x,y;
signed main(){
ios::sync_with_stdio(false);
cin>>n;for(int i=1;i<=n;i++) cin>>a[i]>>b[i],sum*=a[i];
for(int i=1;i<=n;i++){
m[i]=sum/a[i];
exgcd(m[i],a[i],t[i],y);
t[i]=(a[i]+t[i]%a[i])%a[i];
x=x+m[i]*t[i]%sum*b[i]%sum;
}return cout<<x%sum<<'\n',0;
}枚举法
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1012345
int a[N],b[N];
int n,m,sum,ans;
signed main(){
ios::sync_with_stdio(false);
cin>>n;for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}ans=b[1],sum=1;
for(int i=1;i<n;i++){
sum*=a[i];
while(ans%a[i+1]!=b[i+1]) ans+=sum;
}cout<<ans<<'\n';
return 0;
}
