POJ 1061

  题意就不赘诉了，青蛙约会。是一个关于欧几里得扩展的定理的题目

int gcd(int a,int b)//欧几里得求最大公约数
{
if (b==0) return a;
return gcd(b,a%b);
}

int exgcd(int a,int b,int &x,int &y)//欧几里得扩展求ax+by=gcd(a,b)的一组解
{
if (b==0) {x=1;y=0;return a;}
int r=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return r;
}

针对本题，需要注意的是，    1.数据比较大，需要用long long 2.因为是时间，所以x不能是负数，如果出现负数怎么办呢？ a*x1+b*y1=d(d=gcd(a,b)),那个转换成 a*(x1+b*n）+b*（y1-a*n)=d 最终x=(x1%b+b)%b;或者(x1+(abs([x1/b])+1)*b)%b; AC代码：

#include #include #include #include #include using namespace std;

int gcd(int a,int b)
{
if (b==0) return a;
return gcd(b,a%b);
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
if (b==0){ x=1;y=0;return a;}
long long r=exgcd(b,a%b,x,y);
long long t=x;
x=y;
y=t-(a/b)*y;
return r;
}
int main()
{
long long x,y,m,n,L;
cin>>x>>y>>m>>n>>L;
long long s=gcd(n-m,L);
if ((x-y)%s!=0){
cout<<”Impossible”<