Skip to content

Instantly share code, notes, and snippets.

@neetsdkasu
Last active Jul 10, 2021
Embed
What would you like to do?
ModValue (雑)
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<Self>
// From<ModValue> for i64
// From<i64> 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<i64> {
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<Self> {
modinv_eea(self.value, MODULO).map(|value| Self { value })
}
pub fn inv(self) -> Self {
Self {
value: modinv(self.value, MODULO),
}
}
}
impl From<i64> for ModValue {
fn from(value: i64) -> Self {
Self::new(value)
}
}
impl From<ModValue> 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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment