POJ 1601 青蛙的约会
题意是给你两只青蛙，在一个首位相连的数轴上跳，问能否碰到。给出x,y,n,m,l。分别代表第一只所在位置，第二只所在位置，第一只每次跳的步数，第二只每次跳的步数，以及数轴总长度。
稍微化简一下可以发现有 x+m*t=k1*L+p； y+n*t=k2*L+p
得到（n-m)*t+l*(k2-k1)=x-y
可以发现，这是一个二元一次方程，而我们就是要求一对整数解，且（t 是大于0的最小解）
所以就是一道扩展欧几里得算法。
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include<queue>#include<stack>#include<vector>#include<ctype.h>#include<algorithm>#include<string>#define PI acos(-1.0)using namespace std;long long x,y,m,n,l,a,b,d,c;long long gcd(long long a, long long b){ return b == 0 ? a:gcd(b,a%b);}long long X,Y;void ex_gcd(long long a, long long b){ if (!b) { X=1; Y=0; return ; } ex_gcd(b,a%b); long long t = X; X = Y; Y = t - (a/b)*Y;}int main (){ cin>>x>>y>>m>>n>>l; a=n-m; b=l; c=gcd(a,b);// cout<<"c="<<c<<endl; if ((x-y)%c == 0) { ex_gcd(a,b); X *= (x-y)/c; Y *= (x-y)/c;//// cout<<X<<" "<<Y<<endl; long long k=l/c; if (k<0) k=-k; if (X>=0) { X=X-((X/k)+1)*k; while(X<=0) { X+=k; } } else { X=X+((X/k)*(-1)+1)*k; } cout<<X<<endl; } else cout<<"Impossible"<<endl; return 0;}