根据题意，青蛙若想碰面的话，则必有(x+mt)-(y+nt)=p*L;(p为任意整数)。
方程化为：
(m-n)t-(y-x)=pL;则有((m-n)t-(y-x))mod(L)=0(mod为取模运算)。
即为：
(m-n)t mod L=y-x;为线性同余方程。此方程有解当且仅当y-x能被m-n和L的最大公约数(记为gcd(m-n,L)),即gcd(m-n,L)|y-x。这时，如果x0是方程的一个解，即当t=x0时，
(m-n)t mod L=y-x成立，那么所有的解可以表示为：
{x0+k(L/gcd(m-n,L))|(k∈整数)}。
设d=gcd(m-n,L)，根据裴蜀定理，则必存在整数对(r,s)使得(m-n)*r+L*s=d;则可得
t=r*(y-x)/d。证明：把t代入得：
(m-n)t-(y-x)=((m-n)r(y-x)-d(y-x))/d=((y-x)((m-n)r-d))/d=(y-x)*(-L*s)/d.
因为d|y-x,所以L|(y-x)*(-L*s)/d。即
((m-n)t-(y-x))mod(L)=0成立。所以问题转换为求r，也就是解一个含2个数的不定方程
(m-n)*r+L*s=d。
下面在讨论求解不定方程的解法：
求解ax+by=gcd(a,b).
ax+by=gcd(a,b)=gcd(b,a%b)(欧几里德求最大公约数算法)。
gcd(b,a%b)=b*x'+(a%b)*y'.
所以有ax+by=b*x'+(a%b)*y'=b*x'+(a-a/b*b)*y'=ay'+b(x'-a/b*y').
因此由对比系数法得：x=y';y=x'-a/b*y'。
由这个得出扩展的欧几里德算法：
int exGcd(int a, int b, int &x, int &y)
{
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;
}//返回a和b的最大公约数。

• 擦。。。偶然翻到算法导论534页。。意识到自己浪费了N多时间。。。悲·· (37) NARUTOACM 2009-09-26 13:52:04