#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define stacksize 50
struct euclid
{
	long double d;
	long double x;
	long double y;
} eu;
long double mod(long double a,long double b)
{
	long double q=floor(a/b);
	q=a-q*b;
	while(q<0) q+=b;
	while(q>=b) q-=b;
	return q;
}
struct euclid  gcd(long double x,long double y)
{
	struct euclid eu1,eu2;
	if(y==0) 
	{
		eu1.d=x;
		eu1.x=1;
		eu1.y=0;
		return eu1;
	}
	else eu1=gcd(y,floor(mod(x,y)));
	eu2.d=eu1.d;
	eu2.x=eu1.y;
	eu2.y=eu1.x-floor(x/y)*eu1.y;
	return eu2;
}
	
int main()
{
	long double x,y,m,n,L,t,q,min,temp;
	__int64 i;
	scanf("%lf %lf %lf %lf %lf",&x,&y,&m,&n,&L);
	if(x<0) x=x+L;
	if(y<0) y=y+L;
	if(m==n&&x!=y)
	{ 
		printf("Impossible");
		return 0;
	}
	if((m-n<0)) t=m-n+L;
	else t=m-n;
	eu=gcd(t,L);
	if(eu.d!=t*eu.x+L*eu.y)
	{
		temp=eu.x;
		eu.x=eu.y;
		eu.y=temp;
	}
	if((y-x)<0) t=y-x+L;
	else t=y-x;
	if(mod(t,eu.d)!=0) 
	{
		printf("Impossible");
		return 0;
	}
	t=mod((eu.x*(t/eu.d)),L);
	i=0;
	q=t;
	min=q;
	while(i<=eu.d)
	{		
		q=mod((t+(i*(L/eu.d))),L);
		if(min>q) min=q;
		i++;
	}
	i=(__int64)floor(min);
	printf("%ld\n",i);
	system("pause");
  	return 0;
}

• 今天怎么那么多人做这题啊？ (1380) yinxiang1071 2007-01-17 00:03:35
• 扩展欧几里德直接用__int64就可以了 (0) YUMEN19850720 2007-01-17 00:28:28