Codeforces 7C

問題

Ax+By+C=0なる形式で与えられる直線が、格子点を通るかどうか答えよ、という問題。通るなら一つ点を答える。

解答例

拡張ユークリッドの互除法をやるだけ。Ax+Byの0ではない最小値と、そのときのxとyが求まるので、Cがそれで割り切れるかどうか判定するだけ。割り切れればその分xとyを調整すれば格子点の座標になる。