| ||||||||||
| 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