//推出同余式后直接上算法導論結論
#include <iostream>
using namespace std;
__int64 extgcd(__int64 a, __int64 b, __int64 &x, __int64 &y)
{
if(b==0)
{
x=1,y=0;return a;
}
__int64 r=extgcd(b,a%b,x,y);
__int64 t=x; x=y; y=t-a/b*y;
return r;
}
int main()
{
__int64 x,y,m,n,l,k,t;
__int64 a,b,c,d;
while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&n,&m,&l)!=EOF)
{
a=m-n;
b=x-y;
if(m-n<0)
{
a=-a;
b=(-b+l)%l;
}
else b=(b+l)%l;
d=extgcd(a,l,k,t);
if(b%d) { printf("Impossible\n"); continue;}
k=(k*(b/d)%l+l)%(l/d);
printf("%I64d\n", k);
}
return 0;
}
posted on 2010-03-31 22:54
wyiu 閱讀(751)
評論(0) 編輯 收藏 引用 所屬分類:
POJ