haar_lib/math/
ext_gcd.rs

1//! 拡張ユークリッドの互除法
2
3/// 拡張ユークリッドの互除法
4///
5/// # Returns
6/// - `(g, p, q)` : $a * p + m * q = g$を満たす。
7pub fn ext_gcd(a: u64, b: u64) -> (i64, i64, i64) {
8    if b == 0 {
9        return (a as i64, 1, 0);
10    }
11    let (d, q, p) = ext_gcd(b, (a + b) % b);
12    (d, p, q - (a / b) as i64 * p)
13}
14
15#[cfg(test)]
16mod tests {
17    use super::*;
18    use rand::Rng;
19
20    #[test]
21    fn test() {
22        for _ in 0..100 {
23            let mut rng = rand::thread_rng();
24            let n = rng.gen::<u64>() % 1000;
25            let m = rng.gen::<u64>() % 1000;
26            let (g, p, q) = ext_gcd(n, m);
27
28            assert_eq!(n as i64 * p + m as i64 * q, g);
29        }
30    }
31}
haar_lib/math/ext_gcd.rs

haar_lib/math/
ext_gcd.rs
