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:用了扩展欧几里得算法,结果是wa?谁有好的测试数据给我用用,顺便贴上代码,大家帮我看看哪里错了。In Reply To:用了扩展欧几里得算法,结果是wa?谁有好的测试数据给我用用,顺便贴上代码,大家帮我看看哪里错了。 Posted by:DuanYaSong at 2008-02-03 14:04:52 > #include <stdio.h> > #define LONG __int64 > long Euclid_Extended(long a,long b,LONG* x0,LONG* y0); > void main() > { > > long x,y,m,n,l,d,s,c; > LONG x0,y0; > > scanf("%d %d %d %d %d",&x,&y,&m,&n,&l); > > if(m==n) printf("Impossible\n"); > if(m>n) > { > c = (y-x+l)%l; > s=m-n; > } > else > { > c = (x-y+l)%l; > s=n-m; > } > > d=Euclid_Extended(s,l,&x0,&y0); > if(c%d!=0) > { > printf("Impossible\n"); > return ; > } > if(x0>0) > { > x0=x0*(c/d); > y0=-y0*(c/d); > > } > else > { > x0=x0*(c/(-d)); > y0=-y0*(c/(-d)); > } > > x0=x0-y0/(s/d)*(l/d); > > // y0=y0-y0/(s/d)*(s/d); > > printf("%d\n",x0); > } > > long Euclid_Extended(long a,long b,LONG* x0,LONG* y0) > { > LONG t; > long d; > if (b==0) > { > *x0=1; *y0=0; > return a; > } > d=Euclid_Extended(b,a%b,x0,y0); > t=*x0; > *x0=*y0; > *y0=t-a/b*(*y0); > return d; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator