拡張ユークリッドの互除法 (paizaランク C 相当)

割り算から一次方程式の解を求める方法とユークリッドの互除法を応用させると、整数 A , B を用いた一次方程式 Ax + By = gcd(A, B) の整数解 x , y を求めることができます。
この x , y を求めるアルゴリズムを拡張ユークリッドの互除法といいます。
拡張ユークリッドの互除法の疑似コードは以下の通りです。

// ax + by = gcd(a,b) の答えを x , y に代入するプログラム

extgcd(a, b, x のポインタ, y のポインタ) {
  c = a;
  if (b != 0) {
    c = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
  return c;
}

ポインタ変数のない言語を使用する場合は次の疑似コードを参考にしてください。

// ax + by = gcd(a,b) を満たす x, y と gcd(a,b) を返すプログラム

ectgcd(a, b) {
  if b( != 0) {
    c, y, x = extgcd(b, a % b)
    y -= (a / b) * x
    return c, x, y // 最終的に返される c が gcd(a,b) となる
  }
  return a, 1, 0
}

整数 A , B が与えられるので、拡張ユークリッドの互除法を用いて Ax + By = gcd(A, B) の整数解 x , y を求めてください。