cp_library_rs/number_theory/
dynamic_modint.rs

1//! modを動的に設定できるModint
2
3use std::{
4    fmt::{Debug, Display},
5    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
6};
7
8use crate::number_theory::ext_euclid::inv;
9
10/// modを動的に設定できるModint
11#[derive(Clone, Copy, Default, PartialEq, Eq, Hash, Debug)]
12pub struct Modint2 {
13    pub value: usize,
14    pub m: usize,
15}
16
17impl Modint2 {
18    pub fn new(x: usize, m: usize) -> Self {
19        Self { value: x % m, m }
20    }
21
22    pub fn from_isize(x: isize, m: usize) -> Self {
23        Self::new(x.rem_euclid(m as isize) as usize, m)
24    }
25}
26
27impl Neg for Modint2 {
28    type Output = Self;
29    fn neg(self) -> Self {
30        Modint2::new(
31            if self.value == 0 {
32                0
33            } else {
34                self.m - self.value
35            },
36            self.m,
37        )
38    }
39}
40
41impl Add for Modint2 {
42    type Output = Self;
43    fn add(self, rhs: Self) -> Self {
44        assert!(self.m == rhs.m);
45        let mut res = self.value + rhs.value;
46        if res >= self.m {
47            res -= self.m;
48        }
49        Modint2::new(res, self.m)
50    }
51}
52
53impl Sub for Modint2 {
54    type Output = Self;
55    fn sub(self, rhs: Self) -> Self {
56        assert!(self.m == rhs.m);
57        self + (-rhs)
58    }
59}
60
61impl Mul for Modint2 {
62    type Output = Self;
63    fn mul(self, rhs: Self) -> Self {
64        assert!(self.m == rhs.m);
65        Modint2::new(self.value * rhs.value % self.m, self.m)
66    }
67}
68
69impl Div for Modint2 {
70    type Output = Self;
71    fn div(self, rhs: Self) -> Self {
72        assert!(self.m == rhs.m);
73        self * rhs.inv()
74    }
75}
76
77impl AddAssign for Modint2 {
78    fn add_assign(&mut self, rhs: Self) {
79        assert!(self.m == rhs.m);
80        self.value = (*self + rhs).value
81    }
82}
83
84impl SubAssign for Modint2 {
85    fn sub_assign(&mut self, rhs: Self) {
86        assert!(self.m == rhs.m);
87        self.value = (*self - rhs).value
88    }
89}
90
91impl MulAssign for Modint2 {
92    fn mul_assign(&mut self, rhs: Self) {
93        assert!(self.m == rhs.m);
94        self.value = (*self * rhs).value
95    }
96}
97
98impl DivAssign for Modint2 {
99    fn div_assign(&mut self, rhs: Self) {
100        assert!(self.m == rhs.m);
101        self.value = (*self / rhs).value
102    }
103}
104
105impl Add<usize> for Modint2 {
106    type Output = Self;
107    fn add(self, rhs: usize) -> Self {
108        self + Modint2::new(rhs, self.m)
109    }
110}
111
112impl Sub<usize> for Modint2 {
113    type Output = Self;
114    fn sub(self, rhs: usize) -> Self {
115        self - Modint2::new(rhs, self.m)
116    }
117}
118
119impl Mul<usize> for Modint2 {
120    type Output = Self;
121    fn mul(self, rhs: usize) -> Self {
122        self * Modint2::new(rhs, self.m)
123    }
124}
125
126impl Div<usize> for Modint2 {
127    type Output = Self;
128    fn div(self, rhs: usize) -> Self {
129        self / Modint2::new(rhs, self.m)
130    }
131}
132
133impl AddAssign<usize> for Modint2 {
134    fn add_assign(&mut self, rhs: usize) {
135        *self += Modint2::new(rhs, self.m)
136    }
137}
138
139impl SubAssign<usize> for Modint2 {
140    fn sub_assign(&mut self, rhs: usize) {
141        *self -= Modint2::new(rhs, self.m)
142    }
143}
144
145impl MulAssign<usize> for Modint2 {
146    fn mul_assign(&mut self, rhs: usize) {
147        *self *= Modint2::new(rhs, self.m)
148    }
149}
150
151impl DivAssign<usize> for Modint2 {
152    fn div_assign(&mut self, rhs: usize) {
153        *self /= Modint2::new(rhs, self.m)
154    }
155}
156
157impl Display for Modint2 {
158    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
159        write!(f, "{}", self.value)
160    }
161}
162
163impl PartialEq<usize> for Modint2 {
164    fn eq(&self, other: &usize) -> bool {
165        self == &Modint2::new(*other, self.m)
166    }
167}
168
169pub trait Fp {
170    fn pow(&self, rhs: usize) -> Self;
171    /// $`a^{-1}`$ を返す．逆元が存在しない場合はpanicする．
172    fn inv(&self) -> Self;
173}
174
175impl Fp for Modint2 {
176    fn pow(&self, rhs: usize) -> Self {
177        let (mut a, mut b) = (self.value, rhs);
178        let mut res = 1;
179        while b > 0 {
180            if b & 1 == 1 {
181                res = (res * a) % self.m;
182            }
183            a = (a * a) % self.m;
184            b >>= 1u32;
185        }
186        Modint2::new(res, self.m)
187    }
188
189    fn inv(&self) -> Self {
190        let x = inv(self.value as isize, self.m as isize).unwrap() as usize;
191        Modint2::new(x, self.m)
192    }
193}
cp_library_rs/number_theory/dynamic_modint.rs

cp_library_rs/number_theory/
dynamic_modint.rs
