haar_lib/math/
gcd_lcm.rs

1//! 最大公約数・最小公倍数
2
3use std::mem::swap;
4
5/// 最大公約数・最小公倍数
6pub trait GcdLcm {
7    /// GCD,LCMの計算結果の型
8    type Output;
9    /// 最大公約数を求める。
10    fn gcd(self, _: Self::Output) -> Self::Output;
11    /// 最小公倍数を求める。
12    fn lcm(self, _: Self::Output) -> Self::Output;
13    /// 最大公約数と最小公倍数を求める。
14    fn gcd_lcm(self, _: Self::Output) -> (Self::Output, Self::Output);
15}
16
17macro_rules! gcd_lcm_impl_all {
18    ( $($t:ty),* ) => {
19        $(
20            impl GcdLcm for $t {
21                type Output = $t;
22                fn gcd(self, mut b: Self::Output) -> Self::Output {
23                    let mut a = self;
24
25                    if a < b {
26                        swap(&mut a, &mut b);
27                    }
28
29                    if b == 0 {
30                        return a;
31                    }
32
33                    b.gcd(a % b)
34                }
35
36                fn lcm(self, b: Self::Output) -> Self::Output {
37                    self / self.gcd(b) * b
38                }
39
40                fn gcd_lcm(self, b: Self::Output) -> (Self::Output, Self::Output) {
41                    let g = self.gcd(b);
42                    (g, self / g * b)
43                }
44            }
45        )*
46    }
47}
48
49gcd_lcm_impl_all!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test() {
57        assert_eq!(12_i32.gcd_lcm(8), (4, 24));
58    }
59}
haar_lib/math/gcd_lcm.rs

haar_lib/math/
gcd_lcm.rs
