1. paizaラーニングトップ
  2. レベルアップ問題集
  3. ユークリッドの互除法メニュー(言語選択)
  4. 問題一覧 C編
  5. ax + by = c C編

ユークリッドの互除法メニューのサムネイル
ax + by = c C編(paizaランク C 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

ユークリッドの互除法の操作を応用させると、一見最大公約数とは関連のなさそうな 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 が半角スペース区切りで与えられます。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

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

問題一覧へ戻る

ページの先頭へ戻る