首页 > 代码库 > POJ 2891

POJ 2891

线性同余方程组,模板了。但要注意读完数据才跳出循环啊

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;void exgcd(__int64 a,__int64 b,__int64 &d,__int64 &xx,__int64 &yy){	if(b==0){		xx=1;yy=0;d=a;		return ;	}	else{		exgcd(b,a%b,d,xx,yy);		__int64 tmp=xx;		xx=yy;		yy=tmp-(a/b)*yy;	}}int main(){	__int64 n;	__int64 a1,r1,a2,r2; __int64 d,xx,yy;	bool ifhave;	while(scanf("%I64d",&n)!=EOF){		scanf("%I64d%I64d",&a1,&r1);		ifhave=true;		for(__int64 i=1;i<n;i++){			scanf("%I64d%I64d",&a2,&r2);			if(!ifhave) continue;			__int64 a=a1,b=a2,c=r2-r1;			exgcd(a,b,d,xx,yy);			if(c%d!=0){				ifhave=false;			}			__int64 t=b/d;			xx=(xx*(c/d)%t+t)%t;			r1=a1*xx+r1;			a1=a1*(a2/d);		}		if(!ifhave){			printf("-1\n");		}		else printf("%I64d\n",r1);	}	return 0;}

  

POJ 2891