competitive_library/math/
euclid.rs

1//! ユークリッドさんありがとう
2pub fn ngcd(m: u64, n: u64) -> u64 {
3    if m == 0 { n } else { ngcd(n % m, m) }
4}
5pub fn lcm(m: u64, n: u64) -> u64 {
6    m * n / gcd(m, n)
7}
8use std::cmp::min;
9use std::mem::swap;
10pub fn gcd(mut m: u64, mut n: u64) -> u64 {
11    if m == 0 || n == 0 {
12        return n;
13    }
14    let (i, j) = (
15        // unsafe { std::num::NonZeroU64::new_unchecked(m) }.trailing_zeros(),
16        // unsafe { std::num::NonZeroU64::new_unchecked(n) }.trailing_zeros(),
17        m.trailing_zeros(),
18        n.trailing_zeros(),
19    );
20    m >>= i;
21    n >>= j;
22
23    loop {
24        if m > n {
25            swap(&mut m, &mut n);
26        }
27        n -= m;
28        if n == 0 {
29            return m << min(i, j);
30        }
31        // n >>= unsafe { std::num::NonZeroU64::new_unchecked(n) }.trailing_zeros();
32        n >>= n.trailing_zeros();
33    }
34}
35#[cfg(test)]
36mod tests {
37    use super::*;
38    #[test]
39    fn one() {
40        assert_eq!(gcd(1, 2), 1);
41        assert_eq!(gcd(2, 3), 1);
42        assert_eq!(gcd(3, 5), 1);
43        assert_eq!(gcd(5, 7), 1);
44        assert_eq!(gcd(7, 9), 1);
45        assert_eq!(gcd(9, 11), 1);
46        assert_eq!(gcd(11, 13), 1);
47    }
48    #[test]
49    fn t() {
50        assert_eq!(gcd(2, 2), 2);
51        assert_eq!(gcd(2, 4), 2);
52        assert_eq!(gcd(10, 15), 5);
53        assert_eq!(gcd(6, 4), 2);
54        assert_eq!(gcd(100, 30), 10);
55        assert_eq!(gcd(1_000_000_008, 1_000_000_007), 1);
56    }
57}
competitive_library/math/euclid.rs

competitive_library/math/
euclid.rs
