Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
第一次扩展欧几里得 oms AC#include<stdio.h> int gcd(int a,int b) { if(b==0) return a; else return gcd(b,a%b); } void extend_gcd(int a,int b,__int64 &x,__int64 &y) { if(b==0) { x=1; y=0; return ; } else { extend_gcd(b,a%b,x,y); __int64 temp=x; x=y; y=temp-a/b*y; } } int main (void) { int x,y,m,n,l; __int64 x1,y1; int a,b,c; int temp; while(scanf("%d %d %d %d %d",&x,&y,&m,&n,&l)!=EOF) { a=m-n; b=l; temp=b; c=y-x; int r=gcd(a,b); // printf("%d\n",r); if(c%r) printf("Impossible\n"); else { extend_gcd(a,b,x1,y1); // printf("%d\n",r); // printf("%d %d %d %d %d\n",a,b,c,x1,y1); __int64 t=(c*x1/r)/b; x1=c*x1/r-b*t; if(x1<0) x1+=b; printf("%I64d\n",x1); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator