use std::cmp::{max, min};

pub trait UnsignedGCD {
    /// Find the greatest common denominator of two numbers
    fn gcd(a: Self, b: Self) -> Self;

    /// Euclid gcd algorithm
    fn e_gcd(a: Self, b: Self) -> Self;

    /// Stein gcd algorithm
    fn stein_gcd(a: Self, b: Self) -> Self;

    /// Find the least common multiple of two numbers
    fn lcm(a: Self, b: Self) -> Self;
}

macro_rules! impl_unsigned {
    ($($Type: ty),* ) => {
        $(
            impl UnsignedGCD for $Type {
                /// Implementation based on
                /// [Binary GCD algorithm](https://en.wikipedia.org/wiki/Binary_GCD_algorithm)
                fn gcd(a: $Type, b: $Type) -> $Type {
                    if a == b {
                        return a;
                    } else if a == 0 {
                        return b;
                    } else if b == 0 {
                        return a;
                    }

                    let a_even = a % 2 == 0;
                    let b_even = b % 2 == 0;

                    if a_even {
                        if b_even {
                            // Both a & b are even
                            return Self::gcd(a >> 1, b >> 1) << 1;
                        } else if !b_even {
                            // b is odd
                            return Self::gcd(a >> 1, b);
                        }
                    }

                    // a is odd, b is even
                    if (!a_even) && b_even {
                        return Self::gcd(a, b >> 1);
                    }

                    if a > b {
                        return Self::gcd((a - b) >> 1, b);
                    }

                    Self::gcd((b - a) >> 1, a)
                }

                fn e_gcd(x: $Type, y: $Type) -> $Type {
                    let mut x = x;
                    let mut y = y;
                    while y != 0 {
                        let t = y;
                        y = x % y;
                        x = t;
                    }
                    x
                }

                fn stein_gcd(a: Self, b: Self) -> Self {
                    match ((a, b), (a & 1, b & 1)) {
                        ((x, y), _) if x == y => y,
                        ((0, x), _) | ((x, 0), _) => x,
                        ((x, y), (0, 1)) | ((y, x), (1, 0)) => Self::stein_gcd(x >> 1, y),
                        ((x, y), (0, 0)) => Self::stein_gcd(x >> 1, y >> 1) << 1,
                        ((x, y), (1, 1)) => {
                            let (x, y) = (min(x, y), max(x, y));
                            Self::stein_gcd((y - x) >> 1, x)
                        }
                        _ => unreachable!(),
                    }
                }

                fn lcm(a: $Type, b: $Type) -> $Type {
                    if (a == 0 && b == 0) {
                        return 0;
                    }

                    a * b / Self::gcd(a, b)
                }
            }
        )*
    };
}

impl_unsigned!(u8, u16, u32, u64, u128, usize);