//! 拡張ユークリッド互除法

/// 拡張ユークリッド互除法により，
/// $`ax + by = \gcd(a, b)`$ を満たす $`(x, y, \gcd(a,b))`$
/// を求める．
///
/// **戻り値**
/// - `(x, y, gcd(a, b))`
pub fn ext_gcd(a: isize, b: isize) -> (isize, isize, isize) {
    if b == 0 {
        return (1, 0, a);
    }
    let (q, r) = (a / b, a % b);
    let (xx, yy, d) = ext_gcd(b, r);
    let x = yy;
    let y = xx - q * yy;
    (x, y, d)
}

/// 拡張ユークリッド互除法によりモジュラ逆元を計算する．
/// - $`ax \equiv 1 \mod m`$ を満たす $`x`$ を求める．
/// - $`a`$ と $`m`$ は互いに素である必要がある
///
/// **戻り値**
/// - `a`と`m`が互いに素 → Some($`a^{-1} \mod m`$)
/// - `a`と`m`が互いに素でない → None
pub fn inv(a: isize, m: isize) -> Option<isize> {
    let (x, _, d) = ext_gcd(a, m);
    (d == 1).then_some(x.rem_euclid(m))
}