cp_library_rs/number_theory/
ext_euclid.rs

1//! 拡張ユークリッド互除法
2
3/// 拡張ユークリッド互除法により，
4/// $`ax + by = \gcd(a, b)`$ を満たす $`(x, y, \gcd(a,b))`$
5/// を求める．
6///
7/// **戻り値**
8/// - `(x, y, gcd(a, b))`
9pub fn ext_gcd(a: isize, b: isize) -> (isize, isize, isize) {
10    if b == 0 {
11        return (1, 0, a);
12    }
13    let (q, r) = (a / b, a % b);
14    let (xx, yy, d) = ext_gcd(b, r);
15    let x = yy;
16    let y = xx - q * yy;
17    (x, y, d)
18}
19
20/// 拡張ユークリッド互除法によりモジュラ逆元を計算する．
21/// - $`ax \equiv 1 \mod m`$ を満たす $`x`$ を求める．
22/// - $`a`$ と $`m`$ は互いに素である必要がある
23///
24/// **戻り値**
25/// - `a`と`m`が互いに素 → Some($`a^{-1} \mod m`$)
26/// - `a`と`m`が互いに素でない → None
27pub fn inv(a: isize, m: isize) -> Option<isize> {
28    let (x, _, d) = ext_gcd(a, m);
29    (d == 1).then_some(x.rem_euclid(m))
30}

cp_library_rs/number_theory/ext_euclid.rs

cp_library_rs/number_theory/
ext_euclid.rs