pku(1061) 青蛙的约会

作者在 2008-03-04 22:50:45 发布以下内容

程序代码来自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;
}


 


 

acm | 阅读 5452 次
文章评论,共0条
游客请输入验证码
浏览255982次