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 { (0, 0, 0) } else { (1, 0, a) }
19    } else {
20        let (q, r) = (a / b, a % b);
21        // a = bq + r, ax + by = g
22        // -> b * (qx + y) + rx = g
23        let (s, t, g) = ext_gcd(b, r);
24        // s = qx + y
25        // t = x
26        (t, s - q * t, g)
27    }
28}
29
30#[cfg(test)]
31mod tests {
32    use crate::ext_gcd;
33
34    #[test]
35    fn test() {
36        for a in -20..=20 {
37            for b in -20..=20 {
38                let expected_g = gcd(a, b);
39                let (x, y, g) = ext_gcd(a, b);
40                assert_eq!(expected_g, g.abs());
41                assert_eq!(a * x + b * y, g);
42            }
43        }
44    }
45
46    fn gcd(a: i64, b: i64) -> i64 {
47        if a == 0 && b == 0 {
48            return 0;
49        }
50        (1..=(a.abs().max(b.abs())))
51            .filter(|d| a % d == 0 && b % d == 0)
52            .max()
53            .unwrap()
54    }
55}
ext_gcd/lib.rs

ext_gcd/
lib.rs
