問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
ユークリッドの互除法の操作を応用させると、一見最大公約数とは関連のなさそうな 2 変数の一次方程式の整数解を求めることができます。
例として、15x + 100y = 10
の整数解 x , y を求めることを考えます。
x , y の係数である 15 , 100 についてユークリッドの互除法の操作を行うと、100 / 15 = 6 余り 10
この式を変形することで、 100 - 6×15 = 10
が得られるので、答えは x = -6 , y = 1
と求まります。
整数 A,B,C が与えられるので、Ax + By = C
の整数解 x , y の値を 1 行で半角スペース区切りで出力してください。
解の組 (x , y) のうち、x または y が 1 であるような解の組の値を出力してください。
ただし、 C = A%B
または C = B%A
であることが保証されています。
A B C
x y
Ax + By = C
の整数解 x , y の値を 1 行で半角スペース区切りで出力してください。・1 ≦ A , B , C ≦ 100,000
・A ≠ B
・C = A%B
または C = B%A
8373 24 21
1 -348
3 1048 1
-349 1