Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# neetsdkasu/modular.rs

Last active Jul 10, 2021
ModValue (雑)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 mod modular { // author: Leonardone @ NEETSDKASU // modulo for ModValue pub const MODULO: i64 = 1_000_000_007; #[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)] pub struct ModValue { value: i64, } // ModValue::new(i64) -> Self // ModValue::pow(self, i64) -> Self // ModValue::inv(self) -> Self // ModValue::inv_flt(self) -> Self // ModValue::inv_eea(self) -> Option // From for i64 // From for ModValue // Add,Sub,Mul,Div pub fn modinv(v: i64, modulo: i64) -> i64 { if cfg!(using_modinv_eea) { // Extended Euclidean Algorithm (gcd(v,modulo) == 1) modinv_eea(v, modulo).unwrap() } else { // Fermat's little theorem (modulo must be prime) modinv_flt(v, modulo) } } // exp >= 0 pub fn modpow(v: i64, exp: i64, modulo: i64) -> i64 { if exp == 0 { 1 } else if (exp & 1) == 0 { modpow(v * v % modulo, exp >> 1, modulo) } else { v * modpow(v, exp ^ 1, modulo) % modulo } } // Extended Euclidean Algorithm // compute: m*x + n*y = gcd(m, n) // return: (x, y, gcd(m, n)) pub fn extended_euclidean(mut m: i64, mut n: i64) -> (i64, i64, i64) { if m < n { let (y, x, gcd) = extended_euclidean(n, m); return (x, y, gcd); } assert!(m >= n); let mut x = 1; let mut y = 0; let mut u = 0; let mut v = 1; while n != 0 { let k = m / n; // [0 1] [x y] [0*x+1*u 0*y+1*v] // [1 -k] [u v] [1*x-k*u 1*y-k*v] let tx = u; let ty = v; let tu = x - k * u; let tv = y - k * v; x = tx; y = ty; u = tu; v = tv; let t = m % n; m = n; n = t; } (x, y, m) } // calc modular multiplicative inverse // by Fermat's little theorem pub fn modinv_flt(v: i64, prime_modulo: i64) -> i64 { modpow(v, prime_modulo - 2, prime_modulo) } // calc modular multiplicative inverse // by Extended Euclidean Algorithm pub fn modinv_eea(v: i64, modulo: i64) -> Option { let (x, _, gcd) = extended_euclidean(v, modulo); if gcd == 1 { Some(x) } else { None } } impl ModValue { pub fn new(value: i64) -> Self { Self { value: if value < MODULO { value } else { value % MODULO }, } } pub fn pow(self, exp: i64) -> Self { Self { value: modpow(self.value, exp, MODULO), } } pub fn inv_flt(self) -> Self { Self { value: modinv_flt(self.value, MODULO), } } pub fn inv_eea(self) -> Option { modinv_eea(self.value, MODULO).map(|value| Self { value }) } pub fn inv(self) -> Self { Self { value: modinv(self.value, MODULO), } } } impl From for ModValue { fn from(value: i64) -> Self { Self::new(value) } } impl From for i64 { fn from(mod_value: ModValue) -> i64 { mod_value.value } } use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign}; impl Add for ModValue { type Output = Self; fn add(self, other: Self) -> Self::Output { (self.value + other.value).into() } } impl AddAssign for ModValue { fn add_assign(&mut self, other: Self) { *self = *self + other; } } impl Sub for ModValue { type Output = Self; fn sub(self, other: Self) -> Self::Output { (self.value + (MODULO - other.value)).into() } } impl SubAssign for ModValue { fn sub_assign(&mut self, other: Self) { *self = *self - other; } } impl Mul for ModValue { type Output = Self; fn mul(self, other: Self) -> Self::Output { (self.value * other.value).into() } } impl MulAssign for ModValue { fn mul_assign(&mut self, other: Self) { *self = *self * other; } } impl Div for ModValue { type Output = Self; fn div(self, other: Self) -> Self::Output { self.mul(other.inv()) } } impl DivAssign for ModValue { fn div_assign(&mut self, other: Self) { *self = *self / other; } } }
to join this conversation on GitHub. Already have an account? Sign in to comment