题目为POJ1061 青蛙的约会 题意大致为： 两只青蛙在不同的坐标x，y，沿着一个方向跑环，每一次的移动距离为m，n，环的长为L，问能否成功会师即在某一时刻在同一坐标点？输出最小移动次数或“Impossible” 首先是拓展欧几里德，欧几里德算法我们都知道，就是求两个整数a，b的最大公约数gcd，而拓展欧几里德算法在得到gcd的同时，还求解出了ax+by=gcd的一组特解x0和y0，而运用拓展欧几里德算法时，大多都是需要从这个特解找出通解。
ax0 + by0 = gcd ① => ax0+d + by0-d = gcd ② => a(x0+d/a) + b(y0-d/b) = gcd ③ //因此，d最好为a和b的公倍数，那就不妨取d = a*b/gcd; => a(x0+t*d/a) + b(y0-t*d/b)=gcd ④ //t 为任意整数故此，我们可以得到x和y的通解：
x=x0+d/a*t y=y0+d/b*t以上便是拓展欧几里德的知识，那接下来回到问题： 第一只青蛙坐标为x，移动距离m，那 t 次之后它的坐标就是 x+(t*m)，同理，第二只青蛙坐标可表示为 y+(n*t)，然后是根据题意建立等式求最小正整数 t ：
x+(t*m) = y+(n*t) + k*L然后对上式进行变形：
x-y = t*(n-m) + k*L那么，我们假设
A = n-m, B = L, C = x-y，X = t, Y = k;因此不就得到了这样一个式子
AX + BY = C ⑤这跟上面提到的①式只是差了 C 和 gcd；因此，如果 C%gcd==0 ，那么，这个方程就 有解，因为只需把①式的解 *(C/gcd) 就可以得到
x=x0*(C/gcd) + d/a*t y=y0*(C/gcd) + d/b*t //至于后面为什么不乘上(C/gcd) ，好好想下就明白了相反，如果C%gcd！=0 ，就 意味着这个方程无解，而问题的最后是最小t也就是最小的正整数X，因此需要对X进行 一番处理
AC代码
#include<cstdio> #include<iostream> using namespace std; typedef long long ll; ll X, Y; ll exgcd(ll a, ll b) { if(b==0) { X = 1; Y = 0; return a; } ll r = exgcd(b ,a%b); ll t = X; X = Y; Y = t - a/b*X; return r; } int main() { int x, y, m, n, l; cin>>x>>y>>m>>n>>l; ll A = n-m, C = x-y, B = l; ll g = exgcd(A,B); ll D = A*B/g; //题目中明确了x ！= y，因此m == n 方程无解 if(m==n||C%g!=0) puts("Impossible"); else {//X是AX+BY=g方程的一个特解，%(D/A)将其的绝对值化为最小 //乘上（C/g）化为AX+BY=C的特解 ll t = X%(D/A)*(C/g)%(D/A); //t可能是负数，须将其化成最小正整数 if(t < 0) t += (D/A); cout<<t<<endl; } return 0; }