#A1240. 中国剩余定理

前言（Front talk)

数学？使劲凹凹就能过了，还不加油？

网址（Website）

题目详情 - 【NOIP模板】中国剩余定理 - 曹冲养猪 - Super

题解 - 【NOIP模板】中国剩余定理 - 曹冲养猪 - Super

P1495 【模板】中国剩余定理（CRT）

题解（Solution）

中国剩余定理就不用讲了，题解已经讲得够清晰了，只是这几天一直考数学，看到这道题比较妙，有多种解法，于是记录下来。

有问题看 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;
}