#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; 
}

• Re:用了扩展欧几里得算法，结果是wa?谁有好的测试数据给我用用，顺便贴上代码，大家帮我看看哪里错了。 (971) bryantism 2009-10-21 21:03:50
• Re:用了扩展欧几里得算法，结果是wa?谁有好的测试数据给我用用，顺便贴上代码，大家帮我看看哪里错了。 (971) 306457592 2010-03-04 19:43:20