dsalgo/
static_modular_int_i64.rs

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

dsalgo/
static_modular_int_i64.rs
