【ユークリッドの互除法メニュー】ax + by = c (paizaランク C)-解答例-PHP編

ユークリッドの互除法の操作を応用させると、一見最大公約数とは関連のなさそうな 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 であることが保証されています。

入力値（例）
8373 24 21

出力値（例）
1 -348