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 |
Re:测试数据是不是错了?In Reply To:Re:测试数据是不是错了? Posted by:encapsulation at 2006-02-05 15:44:27 #include <math.h> #include <stdio.h> int gcd(int a,int b) { int x=1; int y=1; if (b>a) { x=b; y=a; } else { x=a; y=b; } while (y) { a=y; y=x%y; x=a; } return x; } int fun(int a,int b) { int temp=1; int Q0=1; int Q1=0; int Q2=1; int q=0; int count=0; while (b!=1) { q=a/b; temp=a; Q2=q*Q1+Q0; a=b; b=temp%b; count++; Q0=Q1; Q1=Q2; } if (count%2==0) Q2=-Q2; return Q2; } void main() { int m=0; int n=0; int x=0; int y=0; int L=0; int temp=0; int nGcd=1; scanf("%d%d%d%d%d",&x,&y,&m,&n,&L); if (m==n) { printf("Impossible\n"); return; } nGcd=gcd((int)abs(m-n),L); if ( ((int)abs(x-y))%nGcd!=0 ) { printf("Impossible\n"); return; } if (m-n>0) { L/=nGcd; x=(y-x)/nGcd; m=(m-n)/nGcd; temp=fun(m,L); temp*=x; while (temp<0) temp+=L; if (temp>0) { while (temp>0) temp-=L; temp+=L; } } else if (m-n<0) { L/=nGcd; x=(x-y)/nGcd; m=(n-m)/nGcd; temp=fun(m,L); temp*=x; while (temp<0) temp+=L; if (temp>0) { while (temp>0) temp-=L; temp+=L; } } printf("%d\n",temp); } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator