dsalgo/
modular_int_with_const_modulus_i64.rs

1use std::{
2    marker::PhantomData,
3    ops::*,
4};
5
6use crate::{
7    const_modulus_trait::Modulus,
8    modular_inverse_euclidean_i64_no_error::modinv,
9    multiplicative_inverse::MulInv,
10};
11
12#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
13
14pub struct Modint<M>(pub i64, PhantomData<M>);
15
16impl<M> std::fmt::Display for Modint<M> {
17    fn fmt(
18        &self,
19        f: &mut std::fmt::Formatter,
20    ) -> std::fmt::Result {
21        write!(f, "{}", self.0)
22    }
23}
24
25impl<M: Modulus<T = i64>> Modint<M> {
26    pub fn modulus() -> i64 {
27        M::MOD
28    }
29
30    pub fn normalize(mut v: i64) -> i64 {
31        let m = M::MOD;
32
33        if v < -M::MOD || v >= m {
34            v %= m;
35        }
36
37        if v < 0 {
38            v += m;
39        }
40
41        v
42    }
43
44    pub fn new(v: i64) -> Self {
45        Self(Self::normalize(v), PhantomData)
46    }
47}
48
49impl<M: Modulus<T = i64>> Add for Modint<M> {
50    type Output = Self;
51
52    fn add(
53        mut self,
54        rhs: Self,
55    ) -> Self::Output {
56        self.0 += rhs.0;
57
58        if self.0 >= M::MOD {
59            self.0 -= M::MOD;
60        }
61
62        self
63    }
64}
65
66impl<M: Modulus<T = i64>> Neg for Modint<M> {
67    type Output = Self;
68
69    fn neg(mut self) -> Self::Output {
70        if self.0 != 0 {
71            self.0 = M::MOD - self.0;
72        }
73
74        self
75    }
76}
77
78impl<M: Modulus<T = i64>> Mul for Modint<M> {
79    type Output = Self;
80
81    fn mul(
82        mut self,
83        rhs: Self,
84    ) -> Self::Output {
85        self.0 *= rhs.0;
86
87        if self.0 >= M::MOD {
88            self.0 %= M::MOD;
89        }
90
91        self
92    }
93}
94
95impl<M: Modulus<T = i64>> MulInv for Modint<M> {
96    type Output = Self;
97
98    fn mul_inv(mut self) -> Self::Output {
99        self.0 = modinv(M::MOD, self.0);
100
101        self
102    }
103}
104
105impl<M: Modulus<T = i64>> Sub for Modint<M> {
106    type Output = Self;
107
108    fn sub(
109        self,
110        rhs: Self,
111    ) -> Self::Output {
112        self + -rhs
113    }
114}
115
116impl<M: Modulus<T = i64>> Div for Modint<M> {
117    type Output = Self;
118
119    fn div(
120        self,
121        rhs: Self,
122    ) -> Self::Output {
123        self * rhs.mul_inv()
124    }
125}
126
127impl<M: Modulus<T = i64>> Add<i64> for Modint<M> {
128    type Output = Self;
129
130    fn add(
131        self,
132        rhs: i64,
133    ) -> Self::Output {
134        self + Self::new(rhs)
135    }
136}
137
138impl<M: Modulus<T = i64>> Sub<i64> for Modint<M> {
139    type Output = Self;
140
141    fn sub(
142        self,
143        rhs: i64,
144    ) -> Self::Output {
145        self - Self::new(rhs)
146    }
147}
148
149impl<M: Modulus<T = i64>> Mul<i64> for Modint<M> {
150    type Output = Self;
151
152    fn mul(
153        self,
154        rhs: i64,
155    ) -> Self::Output {
156        self * Self::new(rhs)
157    }
158}
159
160impl<M: Modulus<T = i64>> Div<i64> for Modint<M> {
161    type Output = Self;
162
163    fn div(
164        self,
165        rhs: i64,
166    ) -> Self::Output {
167        self / Self::new(rhs)
168    }
169}
170
171impl<M: Modulus<T = i64>> Add<Modint<M>> for i64 {
172    type Output = Modint<M>;
173
174    fn add(
175        self,
176        rhs: Modint<M>,
177    ) -> Self::Output {
178        Modint::<M>::new(self) + rhs
179    }
180}
181
182impl<M: Modulus<T = i64>> Sub<Modint<M>> for i64 {
183    type Output = Modint<M>;
184
185    fn sub(
186        self,
187        rhs: Modint<M>,
188    ) -> Self::Output {
189        Modint::<M>::new(self) - rhs
190    }
191}
192
193impl<M: Modulus<T = i64>> Mul<Modint<M>> for i64 {
194    type Output = Modint<M>;
195
196    fn mul(
197        self,
198        rhs: Modint<M>,
199    ) -> Self::Output {
200        Modint::<M>::new(self) * rhs
201    }
202}
203
204impl<M: Modulus<T = i64>> Div<Modint<M>> for i64 {
205    type Output = Modint<M>;
206
207    fn div(
208        self,
209        rhs: Modint<M>,
210    ) -> Self::Output {
211        Modint::<M>::new(self) / rhs
212    }
213}
214
215impl<M: Modulus<T = i64> + Copy, T> AddAssign<T> for Modint<M>
216where
217    Self: Add<T, Output = Self>,
218{
219    fn add_assign(
220        &mut self,
221        rhs: T,
222    ) {
223        *self = *self + rhs;
224    }
225}
226
227impl<M: Modulus<T = i64> + Copy, T> SubAssign<T> for Modint<M>
228where
229    Self: Sub<T, Output = Self>,
230{
231    fn sub_assign(
232        &mut self,
233        rhs: T,
234    ) {
235        *self = *self - rhs;
236    }
237}
238
239impl<M: Modulus<T = i64> + Copy, T> MulAssign<T> for Modint<M>
240where
241    Self: Mul<T, Output = Self>,
242{
243    fn mul_assign(
244        &mut self,
245        rhs: T,
246    ) {
247        *self = *self * rhs;
248    }
249}
250
251impl<M: Modulus<T = i64> + Copy, T> DivAssign<T> for Modint<M>
252where
253    Self: Div<T, Output = Self>,
254{
255    fn div_assign(
256        &mut self,
257        rhs: T,
258    ) {
259        *self = *self / rhs;
260    }
261}
262
263impl<M: Modulus<T = i64> + Copy> Modint<M> {
264    pub fn pow(
265        self,
266        n: i64,
267    ) -> Self {
268        if n < 0 {
269            return self.mul_inv().pow(-n);
270        }
271
272        if n == 0 {
273            return Self::new(1);
274        }
275
276        let mut y = self.pow(n >> 1);
277
278        y *= y;
279
280        if n & 1 == 1 {
281            y *= self;
282        }
283
284        y
285    }
286}
287
288impl<M: Modulus<T = i64>> From<i32> for Modint<M> {
289    fn from(x: i32) -> Self {
290        Self::new(x as i64)
291    }
292}
293
294impl<M: Modulus<T = i64>> From<usize> for Modint<M> {
295    fn from(x: usize) -> Self {
296        Self::new(x as i64)
297    }
298}
299
300#[cfg(test)]
301
302mod tests {
303
304    use super::*;
305
306    #[test]
307
308    fn test() {
309        use crate::define_const_modulus_macro::Mod1_000_000_007I64;
310
311        type Mint = Modint<Mod1_000_000_007I64>;
312
313        let mut x = Mint::new(-1);
314
315        assert_eq!(x.0, 1_000_000_006);
316
317        x += 2;
318
319        assert_eq!(x.0, 1);
320
321        assert_eq!((5 * x).0, 5);
322
323        x.0 = 2;
324
325        assert_eq!(x.pow(-1).0, (Mint::modulus() + 1) >> 1);
326    }
327}
dsalgo/modular_int_with_const_modulus_i64.rs

dsalgo/
modular_int_with_const_modulus_i64.rs
