nekolib/math/
gcd.rs

1//! 最大公約数。
2
3/// 最大公約数。
4///
5/// # Complexity
6/// $O(\\log(\\min\\{m, n\\}))$ time.
7///
8/// # Examples
9/// ```
10/// use nekolib::math::Gcd;
11///
12/// assert_eq!(12_u32.gcd(18), 6);
13/// assert_eq!(13_i32.gcd(-3), 1);
14/// assert_eq!(60_u32.gcd(90).gcd(150), 30);
15///
16/// assert_eq!(0_u32.gcd(0), 0);
17/// assert_eq!(0_u32.gcd(1), 1);
18/// ```
19pub trait Gcd {
20    fn gcd(self, other: Self) -> Self;
21}
22
23macro_rules! impl_uint {
24    ($t:ty) => {
25        impl Gcd for $t {
26            fn gcd(mut self, mut other: Self) -> Self {
27                while other > 0 {
28                    let tmp = self % other;
29                    self = std::mem::replace(&mut other, tmp);
30                }
31                self
32            }
33        }
34    };
35    ( $($t:ty)* ) => { $(impl_uint!($t);)* };
36}
37
38macro_rules! impl_int {
39    ($t:ty) => {
40        impl Gcd for $t {
41            fn gcd(mut self, mut other: Self) -> Self {
42                while other != 0 {
43                    let tmp = self.rem_euclid(other);
44                    self = std::mem::replace(&mut other, tmp);
45                }
46                self.abs()
47            }
48        }
49    };
50    ( $($t:ty)* ) => { $(impl_int!($t);)* };
51}
52
53impl_uint!(u8 u16 u32 u64 u128 usize);
54impl_int!(i8 i16 i32 i64 i128 isize);
nekolib/math/gcd.rs

nekolib/math/
gcd.rs
