> #include<iostream.h>
> #include<iomanip.h>
> //x,y用于gcd函数满足：aa*x+nn*y==gcd(aa,nn)
> //gcd返回的值为answer即gcd(cc,dd)==answer
> //e为aa*x==bb(mod nn)的解
> long int x,y,e;
> long int gcd(long int aa,long int bb)
> {
> 	long int t;
> 	long int answer;
> 	if(bb==0)
> 	{
> 		answer=aa;
> 		x=1;
> 		y=0;
> 	}
> 	else
> 	{
> 		answer=gcd(bb,aa%bb);
> 		t=x;
> 		x=y;
> 		y=t-(aa/bb)*y;
> 	}
> 	return answer;
> }
> void tongyu(long int aa,long int bb,long int nn)
> {
> 	long int d,i,ee;
> 	d=gcd(aa,nn);
> 	if(bb%d>0)
> 	{
> 		e=-1;
> 		return;
> 	}
> 	else
> 	{
> 		e=(x*(bb/d))%nn;
> 		if(e<0)
> 			e=e+nn;
> 		
> 	}
> }
> int main()
> {long int x1,y1,x2,y2,m,n,l,b;
> 
> cin>>x2>>y2>>m>>n>>l;
> cout << setprecision(0);
> cout << setiosflags(ios::fixed);
>   x1=x2%l;
>   y1=y2%l;
>   if(m>=n)
>   {
> 	  if(y1>=x1)
> 		  b=y1-x1;
> 	  else
> 		  b=y1-x1+l;
> 	  tongyu(m-n,b,l);
>       if(e==-1)
> 	  {
> 	  cout<<"Impossible"<<endl;
> 	  }
>       else
> 	  {
> 	     cout<<e<<endl;
> 	  }
>   }
>   if(m<n)
>   {
> 	  if(x1>=y1)
> 	  {
> 		  b=x1-y1;
> 	  }
> 	  else
> 		  b=x1-y1+l;
> 	  tongyu(n-m,b,l);
> 	  if(e==-1)
> 	  {
> 	  cout<<"Impossible"<<endl;
> 	  }
>       else
> 	  {
> 	     cout<<e<<endl;
> 	  }
>   }
> 
>   return 0;
> }

//彻底int64就可

#include <stdio.h>
#define int64 __int64

void ExtEuclid(int64 a,int64 b,int64& d,int64& x,int64& y)
{ int64 temp;
 if (b==0)
  {d=a; x=1; y=0;
   return;
  }
 ExtEuclid(b,a%b,d,x,y);
 temp=x-y*(a/b);
 x=y; y=temp;
}

int main()
{int64 x,y,m,n,l,a,b,d,u,v,ans;
 scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l);
 a=(l+m-n)%l; b=(l+y-x)%l;
 ExtEuclid(a,l,d,u,v);
 if (b%d!=0)
  printf("Impossible\n");
 else
  {ans=(u*(b/d)%l);
   if (ans<0) ans+=l;
   ans=ans%(l/d);
   printf("%I64d\n",ans);
  }
 return 0;
}

• 谢谢啦 (627) fdfzq 2004-02-07 10:23:29
• 不用彻底int64 (98) iscxy 2005-07-14 03:17:59