首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。