1061.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"stdio.h"
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;
_int64 M,N,T;
scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l);
//cin>>x>>y>>m>>n>>l;
if(m>n){b=(l+y-x)%l;a=(l+m-n)%l;}
if(m<n){b=(l+x-y)%l;a=(l+n-m)%l;}
if(m==n){printf("Impossible\n");
          
		  return 1;}
ExtEuclid(a,l,T,M,N);
if(b%T!=0){printf("Impossible\n");return 1;}

M=M*(b/T)%l;

if(M<0)M+=l;
M%=(l/T);
printf("%I64d\n",M);


return 1;}