P1495 【模板】中国剩余定理(CRT)/曹冲养猪 题解

Link

P1495 【模板】中国剩余定理(CRT)/曹冲养猪

Solve

莫名其妙跑来刷数论------不自量力

中国剩余定理的板子题，比较水，就是有个细节

解同余方程时(aequiv1pmod{m})可能会解出负的，所以加上(m)重新模一次就好了

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=15;
int N,B[maxn],W[maxn];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;y=0;
		return a;
	}
	int gcd=exgcd(b,a%b,x,y);
	int t=x;x=y;y=t-a/b*y;
	return gcd;
}
signed main(){
	freopen("P1495.in","r",stdin);
	freopen("P1495.out","w",stdout);
	N=read();
	int x,y,a=0,m,n=1;
	for(int i=1;i<=N;i++)W[i]=read(),B[i]=read(),n*=W[i];
	for(int i=1;i<=N;i++){
		m=n/W[i];
		exgcd(W[i],m,x,y);
		a=(a+(y<0?y+W[i]:y)*m*B[i])%n;
	}
	cout<<a<<endl;
	return 0;
}