Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:用了扩展欧几里得算法,结果是wa?谁有好的测试数据给我用用,顺便贴上代码,大家帮我看看哪里错了。

Posted by 306457592 at 2010-03-04 19:43:20 on Problem 1061
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator