Codeforces #7 C Line

問題目超短，問的是﹕給了A, B, C (-2*10^9 <= A, B, C <= -2*10^9)，問有否存在一點P在線Ax+By+C=0並且P的x-y座標均是整數，且在-5*10^18至5*10^18以內。沒有的話則輸出-1。保証A^2+B^2 > 0。

先處理special case﹕ A=0 或 B=0的情況(因A^2+B^2 > 0 所以不會出現A=B=0的情況)。直接方法就是檢查B|-C或A|-C即可。

一般的情況，即Ax+By+C=0並且|A|, |B| > 0，可以直接看成找出如下問題﹕
x = (-C-By)/A，問有否存在整數y使得x為整數。

等價問題﹕
By = -C (mod A)，求y。

注意，如果A是負數的話，則把A, B, C替換成-A, -B, -C，再解決同一問題。

記得預先把B, C取模A。剩下的就是為如下式求解﹕
Py = Q (mod A)， P = B (mod A), Q = -C (mod A)

比較經典的問題。首先，求R = gcd(A, P)。如果R|Q則有解，否則無解。
有解的話，則把P, Q, A換成S = P/R, T = Q/R, U = A/R，再解如下式﹕
Sy = T (mod U)
因為S, U互質，則可以用擴展歐幾里特算法，找到S^-1。
y = TS^-1 (mod U)

然後可以直接用y求x。問題是﹕x, y的值會否分別超出題目要求的上限？注意﹕求出的y是模U的，而U則是取值[-2*10^9, 2*10^9]，因此x = (-C-By)/A 取值[-4*10^18-2*10^9, 4*10^18+2*10^9]，不會超出上限。