自然数/整数 - 関数 - 拡張ユークリッド互除法

概要

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

/// Number - Extended GCD on Integers
use crate::num::base::*;
pub fn gcd_ex<N: Int>(x: N, y: N) -> (N, N, N) {
    let mut r0 = x;
    let mut a0 = N::one();
    let mut b0 = N::zero();
    let mut r = y;
    let mut a = N::zero();
    let mut b = N::one();
    while r > N::zero() {
        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)
}

#[cfg(test)]
mod test_gcd {
    use crate::num::gcd_ex::*;

    #[test]
    fn it_works() {
        assert_eq!(gcd_ex(3_i32, 5), (2, -1, 1));
        assert_eq!(gcd_ex(3_i64, 6), (1, 0, 3));
    }
}