ax + by = c Bash(Beta)編（paizaランク C 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
ユークリッドの互除法の操作を応用させると、一見最大公約数とは関連のなさそうな 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
・1 行で、整数 A , B , C が半角スペース区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
x y
・Ax + By = Cの整数解 x , y の値を 1 行で半角スペース区切りで出力してください。
・x または y が 1 であるような解の組 (x , y) の値を出力してください。
・また、出力の末尾には改行を入れてください。
- 条件
-
・1 ≦ A , B , C ≦ 100,000
・A ≠ B
・C = A%BまたはC = B%A
- 入力例1
-
8373 24 21
- 出力例1
-
1 -348
- 入力例2
-
3 1048 1
- 出力例2
-
-349 1
