拡張ユークリッド互除法

\(0\) でない整数の組 \((x, y)\) について、 \[ax + by = c\] なる整数の組 \((a, b, c)\) を返す. ここで \(c = gcd(x, y)\).

Rust

fn ex_gcd(x: i32, y: i32) -> (i32, i32, i32) {
    let mut r0 = x;
    let mut a0 = 1;
    let mut b0 = 0;
    let mut r = y;
    let mut a = 0;
    let mut b = 1;
    while r > 0 {
        let (r2, a2, b2) = (r0 % r, a0 - r0 / r * a, b0 - r0 / r * b);
        r0 = r; r = r2;
        a0 = a; a = a2;
        b0 = b; b = b2;
    }
    (a0, b0, r0)
}

C++

tuple<int, int, int> ex_gcd(int x, int y) {
  int r0 = x, a0 = 1, b0 = 0;
  for (int r = y, a = 0, b = 1; r > 0; ) {
    int r2 = r0 % r;
    int a2 = a0 - r0 / r * a;
    int b2 = b0 - r0 / r * b;
    r0 = r; r = r2;
    a0 = a; a = a2;
    b0 = b; b = b2;
  }
  return make_tuple(a0, b0, r0);
}