POJ 1061 青蛙的约会 扩展欧几里得http://poj.org/problem?id=1061
来源：http://poj.org/problem?id=1061
题意：中文题。。。
思路：由题意易知，posx + vx * t – posy – vy * t = k * L，也就是说解该方程的解。该方程经过化简后可以写为 t*(vx - vy) – k * L = posy – posx，进一步化简为 k*L + t * (vy- vx) = posx – posy,L和(vx - vy)都可以求出来，也就是说是已知的。该方程是我们比较熟悉的，也就是常见的扩展欧几里得方程的形式。
此时，令 gcdx = gcd(L,vy - vx)，若(posx – posy) % gcdx == 0,则该方程有解，也就是说青蛙可以碰见，否则是碰不到的。
接下来运用扩展欧几里得就可以了，至于扩展欧几里得的知识，网上有很多，这里就不多说了。当我们用扩展欧几里得求出ax + by = 1的一组解后，我们需要求最小的正整数解。对题目来说，就是t必须为正整数，若求出的特解为负数，这时我们需要处理一下。
ax + by = pos 此时又一组解，其中y是负数。我们的目的是使得y变为满足方程的最小正数。现在我们把方程改变一下。ax – kab + by + kab = pos,方程实质是没有改变的,我们在化简一下，变成a(x- kb) + b (y + ka) = pos，使y变正，只需要加若干个a即可，具体数目可以算出来。
代码：
#include <iostream>#include <cstdio>#include <string.h>using namespace std;#define CLR(arr,val) memset(arr,val,sizeof(arr))typedef long long ll;ll xx,yy;ll gcd(ll a,ll b){ if(b == 0) return a; return gcd(b,a%b);}void extend_Eulid(ll a,ll b){if(b == 0){ xx = 1; yy = 0; return;}else{ extend_Eulid(b,a%b); int temp = xx; xx = yy; yy = temp - a/b * yy;}}int main(){//freopen("1.txt","r",stdin);//freopen("3.txt","w",stdout);ll posx,posy,vx,vy,L;while(scanf("%lld%lld%lld%lld%lld",&posx,&posy,&vx,&vy,&L) != EOF){ll dvx = vy - vx;ll dpos = posx - posy; ll gcdx = gcd(L,dvx); if(dpos % gcdx){ printf("Impossible\n"); } else{dvx = dvx / gcdx;dpos = dpos / gcdx;L /= gcdx;extend_Eulid(L,dvx);yy *= dpos;xx *= dpos;if(L < 0) L = -L;if(yy > 0 && xx > 0) yy %= L;else{ll cnt = yy/L;cnt = -cnt;cnt++; yy = (yy + L * cnt)%L;}printf("%lld\n",yy); }}return 0;}