An integer mod n.

mod_int.rs

use num::{One, Zero};

/// An integer mod n.
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ModInt<const MOD: u64>(u64);

impl<const MOD: u64> ModInt<MOD> {
    pub fn as_u64(self) -> u64 {
        self.0
    }

    pub fn pow(mut self, mut exp: u32) -> Self {
        if exp == 0 {
            return Self(1);
        }
        let mut y = Self(1);
        while 1 < exp {
            if exp % 2 == 0 {
                self = self * self;
            } else {
                y = self * y;
                self = self * self;
                exp -= 1;
            }
            exp /= 2;
        }
        self * y
    }

    pub fn factorial(self) -> Self {
        let mut result = Self(1);
        for x in 2..=self.0 {
            result *= Self(x);
        }
        result
    }
}

macro_rules! impl_from_for_mod_int {
    ($t:ty) => {
        impl<const MOD: u64> From<$t> for ModInt<MOD> {
            fn from(x: $t) -> Self {
                Self(x as u64 % MOD)
            }
        }
        impl<const MOD: u64> From<&'_ $t> for ModInt<MOD> {
            fn from(&x: &'_ $t) -> Self {
                Self(x as u64 % MOD)
            }
        }
    };
}

impl_from_for_mod_int!(u64);
impl_from_for_mod_int!(u32);
impl_from_for_mod_int!(usize);
impl_from_for_mod_int!(i32);

impl<const MOD: u64> std::ops::Add for ModInt<MOD> {
    type Output = Self;
    fn add(self, rhs: Self) -> Self::Output {
        Self((self.0 + rhs.0) % MOD)
    }
}

impl<const MOD: u64> std::ops::AddAssign for ModInt<MOD> {
    fn add_assign(&mut self, rhs: Self) {
        self.0 += rhs.0;
        self.0 %= MOD;
    }
}

impl<const MOD: u64> std::ops::Sub for ModInt<MOD> {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self::Output {
        Self((self.0 + MOD - rhs.0) % MOD)
    }
}

impl<const MOD: u64> std::ops::SubAssign for ModInt<MOD> {
    fn sub_assign(&mut self, rhs: Self) {
        while self.0 < rhs.0 {
            self.0 += MOD;
        }
        self.0 -= rhs.0;
        self.0 %= MOD;
    }
}

impl<const MOD: u64> std::ops::Mul for ModInt<MOD> {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self::Output {
        Self((self.0 * rhs.0) % MOD)
    }
}

impl<const MOD: u64> std::ops::MulAssign for ModInt<MOD> {
    fn mul_assign(&mut self, rhs: Self) {
        self.0 *= rhs.0;
        self.0 %= MOD;
    }
}

impl<const MOD: u64> std::ops::Div for ModInt<MOD> {
    type Output = Self;
    fn div(self, rhs: Self) -> Self::Output {
       self * rhs.pow(MOD as u32 - 2)
    }
}

impl<const MOD: u64> std::ops::DivAssign for ModInt<MOD> {
    fn div_assign(&mut self, rhs: Self) {
        *self = *self / rhs;
    }
}

impl<const MOD: u64> std::ops::Neg for ModInt<MOD> {
    type Output = Self;

    fn neg(self) -> Self::Output {
        Self(MOD - self.0)
    }
}

impl<const MOD: u64> std::ops::Rem for ModInt<MOD> {
    type Output = Self;

    fn rem(self, rhs: Self) -> Self::Output {
        Self(self.0 % rhs.0 % MOD)
    }
}

impl<const MOD: u64> std::iter::Sum for ModInt<MOD> {
    fn sum<I>(iter: I) -> Self
    where
        I: Iterator<Item = Self>,
    {
        iter.fold(Self(0), |a, b| a + b)
    }
}

impl<const MOD: u64> std::iter::Product for ModInt<MOD> {
    fn product<I>(iter: I) -> Self
    where
        I: Iterator<Item = Self>,
    {
        iter.fold(Self(1), |a, b| a * b)
    }
}

impl<const MOD: u64> Zero for ModInt<MOD> {
    fn zero() -> Self {
        Self(0)
    }

    fn is_zero(&self) -> bool {
        self.0 == 0
    }
}

impl<const MOD: u64> One for ModInt<MOD> {
    fn one() -> Self {
        Self(1)
    }
}