POJ1061 青蛙的約會 （擴充歐幾裡德）

本文出自：

題意：青蛙繞圈跳， 初始位置x，y，速度m，n，方向相反，l為模。最後能否相遇？相遇時間是什麼？

本題目為擴充歐幾裡德，擴充歐幾裡德介紹：

關于擴充歐幾裡德方程

ax + by = c

(1)

可以用來求是否有解。即是否存在c滿足這個方程。

exgcd(a, b, x, y)是用來求ax + by = gcd(a, b)中x的值和y的值的。如果僅僅隻是判斷(1)是否有解，直接看gcd(a, b)能否整除c即可。

然後開始分析本題：

設最後在坐标s相遇，a轉了b圈，b轉了b`圈，花費時間為a，那麼可以得到兩個方程：

ma + x = lb + s;

（3）

na + y = lb` + s;

（4）

如果s有解，那麼方程 (m - n)a+l(b - b`) = y - x有解。（即(3) - (4))

以此判斷impossible的情況;（一開始做的時候沒弄懂題意，以為不同方向，shit- -）

解出的a可能不是一個正數，或者比最小數大。

通解為

x1 = x + l / gcd(m-n, l) * t;

t為任意整數;

y1 = y - l / gcd(m-n,l) * t;

證明：

已知ax  + by  = c

ax1 = x * a + lcm(a, b) * t;

by1 = y * b - lcm(a, b)*t;

是以ax1 + by1 = c;

代碼如下：