POJ1061——青蛙的约会（扩展GCD应用）

本文主要是介绍POJ1061——青蛙的约会（扩展GCD应用），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意是这样的:

设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。 

可以看出来这是一个同余方程问题，可以利用扩展GCD进行求解，具体方法参见扩展欧几里得的应用。

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#define INF 0x7fffffff
using namespace std;
typedef long long LL;
void gcd(LL a,LL b,LL& d,LL& x,LL& y)
{if(!b) {d=a; x=1; y=0;}else {gcd(b, a%b, d, y, x); y-=x*(a/b); }
}
int main()
{LL x,y,n,m,L;LL xx,yy,d;while(cin>>x>>y>>m>>n>>L){gcd(n-m,L,d,xx,yy);if((x-y)%d!=0) {cout<<"Impossible"<<endl;continue;}LL s=L/d;if(s<0) s=-s;xx*=(x-y)/d;xx=(xx%s+s)%s;cout<<xx<<endl;}return 0;
}

这篇关于POJ1061——青蛙的约会（扩展GCD应用）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---