程序代码来自redcastle,我看了很多的关于一元同余方程的解释,都不是很名白,今天在redcastle的博客上看到了他的解释恍然大悟,终于把1061给AC了,http://hi.baidu.com/redcastle/blog/item/e6dc30d3a5574d023af3cfe0.html是代码,
http://hi.baidu.com/redcastle/blog/item/934b232dbc40d336349bf7e4.html关于一元同余方程的解释。
我还是把我代码写出来
#include <iostream>
using namespace std;
struct strple
{
int x,y,r;
};
__int64 mod(__int64 a,__int64 b)
{
return (a%b+b)%b;
}
int Euild(int a, int b)
{
if(b==0)
return a;
else
return Euild(b,mod(a,b));
}
strple Extrend_Euild(__int64 a,__int64 b)
{
strple result;
if(b==0)
{
result.x=1;
result.y=0;
result.r=a;
}
else{
strple ee=Extrend_Euild(b,mod(a,b));
result.x=ee.y;
result.y=ee.x-(a/b)*ee.y;
result.r=ee.r;
}
return result;
}
__int64 MLES(__int64 a,__int64 b, __int64 n)
{
strple ee=Extrend_Euild(a,n);
if(mod(b,ee.r)==0)
return mod(ee.x*(b/ee.r),n/ee.r);
else
return -1;
}
int main()
{
__int64 x,y,m,n,l;
while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l)!=EOF)
{
__int64 mles;
mles=MLES(m-n,y-x,l);
if(mles<0)
cout<<"Impossible"<<endl;
else
printf("%I64d\n",mles);
}
return 0;
}