ext_gcd/
lib.rs

1/// g = gcd(a, b), ax + by = g を満たす (x, y, g) を返します。
2///
3/// # Examples
4/// ```
5/// use ext_gcd::ext_gcd;
6///
7/// let (x, y, g) = ext_gcd(48, 30);
8/// assert_eq!(g, 6);
9/// assert_eq!(48 * x + 30 * y, g); // e.g. x = 2, y = -3
10///
11/// assert_eq!(ext_gcd(42, 0), (1, 0, 42));
12/// assert_eq!(ext_gcd(0, 0), (0, 0, 0));
13/// ```
14#[allow(clippy::many_single_char_names)]
15pub fn ext_gcd(a: i64, b: i64) -> (i64, i64, i64) {
16    if b == 0 {
17        // ax + 0y = a
18        if a == 0 {
19            (0, 0, 0)
20        } else {
21            (1, 0, a)
22        }
23    } else {
24        let (q, r) = (a / b, a % b);
25        // a = bq + r, ax + by = g
26        // -> b * (qx + y) + rx = g
27        let (s, t, g) = ext_gcd(b, r);
28        // s = qx + y
29        // t = x
30        (t, s - q * t, g)
31    }
32}
33
34#[cfg(test)]
35mod tests {
36    use crate::ext_gcd;
37
38    #[test]
39    fn test() {
40        for a in -20..=20 {
41            for b in -20..=20 {
42                let expected_g = gcd(a, b);
43                let (x, y, g) = ext_gcd(a, b);
44                assert_eq!(expected_g, g.abs());
45                assert_eq!(a * x + b * y, g);
46            }
47        }
48    }
49
50    fn gcd(a: i64, b: i64) -> i64 {
51        if a == 0 && b == 0 {
52            return 0;
53        }
54        (1..=(a.abs().max(b.abs())))
55            .filter(|d| a % d == 0 && b % d == 0)
56            .max()
57            .unwrap()
58    }
59}
ext_gcd/lib.rs

ext_gcd/
lib.rs
