1use super::*;
2
3use std::{
4 fmt::{self, Debug, Display},
5 hash::{Hash, Hasher},
6 iter::{Product, Sum},
7 marker::PhantomData,
8 ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
9 str::FromStr,
10};
11
12#[repr(transparent)]
13pub struct MInt<M>
14where
15 M: MIntBase,
16{
17 x: M::Inner,
18 _marker: PhantomData<fn() -> M>,
19}
20
21pub trait MIntConvert<T = <Self as MIntBase>::Inner>: MIntBase {
22 fn from(x: T) -> <Self as MIntBase>::Inner;
23 fn into(x: <Self as MIntBase>::Inner) -> T;
24 fn mod_into() -> T;
25}
26
27pub trait MIntBase {
28 type Inner: Sized + Copy + Eq + Debug + Hash;
29 fn get_mod() -> Self::Inner;
30 fn mod_zero() -> Self::Inner;
31 fn mod_one() -> Self::Inner;
32 fn mod_add(x: Self::Inner, y: Self::Inner) -> Self::Inner;
33 fn mod_sub(x: Self::Inner, y: Self::Inner) -> Self::Inner;
34 fn mod_mul(x: Self::Inner, y: Self::Inner) -> Self::Inner;
35 fn mod_div(x: Self::Inner, y: Self::Inner) -> Self::Inner;
36 fn mod_neg(x: Self::Inner) -> Self::Inner;
37 fn mod_inv(x: Self::Inner) -> Self::Inner;
38 fn mod_pow(x: Self::Inner, y: usize) -> Self::Inner {
39 let (mut x, mut y, mut z) = (x, y, Self::mod_one());
40 while y > 0 {
41 if y & 1 == 1 {
42 z = Self::mod_mul(z, x);
43 }
44 x = Self::mod_mul(x, x);
45 y >>= 1;
46 }
47 z
48 }
49 fn mod_inner(x: Self::Inner) -> Self::Inner {
50 x
51 }
52}
53
54impl<M> MInt<M>
55where
56 M: MIntConvert,
57{
58 #[inline]
59 pub fn new(x: M::Inner) -> Self {
60 Self::new_unchecked(<M as MIntConvert<M::Inner>>::from(x))
61 }
62}
63impl<M> MInt<M>
64where
65 M: MIntBase,
66{
67 #[inline]
68 pub const fn new_unchecked(x: M::Inner) -> Self {
69 Self {
70 x,
71 _marker: PhantomData,
72 }
73 }
74 #[inline]
75 pub fn get_mod() -> M::Inner {
76 M::get_mod()
77 }
78 #[inline]
79 pub fn pow(self, y: usize) -> Self {
80 Self::new_unchecked(M::mod_pow(self.x, y))
81 }
82 #[inline]
83 pub fn inv(self) -> Self {
84 Self::new_unchecked(M::mod_inv(self.x))
85 }
86 #[inline]
87 pub fn inner(self) -> M::Inner {
88 M::mod_inner(self.x)
89 }
90}
91
92impl<M> Clone for MInt<M>
93where
94 M: MIntBase,
95{
96 #[inline]
97 fn clone(&self) -> Self {
98 *self
99 }
100}
101impl<M> Copy for MInt<M> where M: MIntBase {}
102impl<M> Debug for MInt<M>
103where
104 M: MIntBase,
105{
106 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
107 Debug::fmt(&self.inner(), f)
108 }
109}
110impl<M> Default for MInt<M>
111where
112 M: MIntBase,
113{
114 #[inline]
115 fn default() -> Self {
116 <Self as Zero>::zero()
117 }
118}
119impl<M> PartialEq for MInt<M>
120where
121 M: MIntBase,
122{
123 #[inline]
124 fn eq(&self, other: &Self) -> bool {
125 PartialEq::eq(&self.x, &other.x)
126 }
127}
128impl<M> Eq for MInt<M> where M: MIntBase {}
129impl<M> Hash for MInt<M>
130where
131 M: MIntBase,
132{
133 #[inline]
134 fn hash<H: Hasher>(&self, state: &mut H) {
135 Hash::hash(&self.x, state)
136 }
137}
138macro_rules! impl_mint_from {
139 ($($t:ty),*) => {
140 $(impl<M> From<$t> for MInt<M>
141 where
142 M: MIntConvert<$t>,
143 {
144 #[inline]
145 fn from(x: $t) -> Self {
146 Self::new_unchecked(<M as MIntConvert<$t>>::from(x))
147 }
148 }
149 impl<M> From<MInt<M>> for $t
150 where
151 M: MIntConvert<$t>,
152 {
153 #[inline]
154 fn from(x: MInt<M>) -> $t {
155 <M as MIntConvert<$t>>::into(x.x)
156 }
157 })*
158 };
159}
160impl_mint_from!(
161 u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize
162);
163impl<M> Zero for MInt<M>
164where
165 M: MIntBase,
166{
167 #[inline]
168 fn zero() -> Self {
169 Self::new_unchecked(M::mod_zero())
170 }
171}
172impl<M> One for MInt<M>
173where
174 M: MIntBase,
175{
176 #[inline]
177 fn one() -> Self {
178 Self::new_unchecked(M::mod_one())
179 }
180}
181
182impl<M> Add for MInt<M>
183where
184 M: MIntBase,
185{
186 type Output = Self;
187 #[inline]
188 fn add(self, rhs: Self) -> Self::Output {
189 Self::new_unchecked(M::mod_add(self.x, rhs.x))
190 }
191}
192impl<M> Sub for MInt<M>
193where
194 M: MIntBase,
195{
196 type Output = Self;
197 #[inline]
198 fn sub(self, rhs: Self) -> Self::Output {
199 Self::new_unchecked(M::mod_sub(self.x, rhs.x))
200 }
201}
202impl<M> Mul for MInt<M>
203where
204 M: MIntBase,
205{
206 type Output = Self;
207 #[inline]
208 fn mul(self, rhs: Self) -> Self::Output {
209 Self::new_unchecked(M::mod_mul(self.x, rhs.x))
210 }
211}
212impl<M> Div for MInt<M>
213where
214 M: MIntBase,
215{
216 type Output = Self;
217 #[inline]
218 fn div(self, rhs: Self) -> Self::Output {
219 Self::new_unchecked(M::mod_div(self.x, rhs.x))
220 }
221}
222impl<M> Neg for MInt<M>
223where
224 M: MIntBase,
225{
226 type Output = Self;
227 #[inline]
228 fn neg(self) -> Self::Output {
229 Self::new_unchecked(M::mod_neg(self.x))
230 }
231}
232impl<M> Sum for MInt<M>
233where
234 M: MIntBase,
235{
236 #[inline]
237 fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
238 iter.fold(<Self as Zero>::zero(), Add::add)
239 }
240}
241impl<M> Product for MInt<M>
242where
243 M: MIntBase,
244{
245 #[inline]
246 fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
247 iter.fold(<Self as One>::one(), Mul::mul)
248 }
249}
250impl<'a, M: 'a> Sum<&'a MInt<M>> for MInt<M>
251where
252 M: MIntBase,
253{
254 #[inline]
255 fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
256 iter.fold(<Self as Zero>::zero(), Add::add)
257 }
258}
259impl<'a, M: 'a> Product<&'a MInt<M>> for MInt<M>
260where
261 M: MIntBase,
262{
263 #[inline]
264 fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
265 iter.fold(<Self as One>::one(), Mul::mul)
266 }
267}
268impl<M> Display for MInt<M>
269where
270 M: MIntBase,
271 M::Inner: Display,
272{
273 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
274 write!(f, "{}", self.inner())
275 }
276}
277impl<M> FromStr for MInt<M>
278where
279 M: MIntConvert,
280 M::Inner: FromStr,
281{
282 type Err = <M::Inner as FromStr>::Err;
283 #[inline]
284 fn from_str(s: &str) -> Result<Self, Self::Err> {
285 s.parse::<M::Inner>().map(Self::new)
286 }
287}
288impl<M> IterScan for MInt<M>
289where
290 M: MIntConvert,
291 M::Inner: FromStr,
292{
293 type Output = Self;
294 #[inline]
295 fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
296 iter.next()?.parse::<MInt<M>>().ok()
297 }
298}
299macro_rules! impl_mint_ref_binop {
300 ($imp:ident, $method:ident, $t:ty) => {
301 impl<M> $imp<$t> for &$t
302 where
303 M: MIntBase,
304 {
305 type Output = <$t as $imp<$t>>::Output;
306 #[inline]
307 fn $method(self, other: $t) -> <$t as $imp<$t>>::Output {
308 $imp::$method(*self, other)
309 }
310 }
311 impl<M> $imp<&$t> for $t
312 where
313 M: MIntBase,
314 {
315 type Output = <$t as $imp<$t>>::Output;
316 #[inline]
317 fn $method(self, other: &$t) -> <$t as $imp<$t>>::Output {
318 $imp::$method(self, *other)
319 }
320 }
321 impl<M> $imp<&$t> for &$t
322 where
323 M: MIntBase,
324 {
325 type Output = <$t as $imp<$t>>::Output;
326 #[inline]
327 fn $method(self, other: &$t) -> <$t as $imp<$t>>::Output {
328 $imp::$method(*self, *other)
329 }
330 }
331 };
332}
333impl_mint_ref_binop!(Add, add, MInt<M>);
334impl_mint_ref_binop!(Sub, sub, MInt<M>);
335impl_mint_ref_binop!(Mul, mul, MInt<M>);
336impl_mint_ref_binop!(Div, div, MInt<M>);
337macro_rules! impl_mint_ref_unop {
338 ($imp:ident, $method:ident, $t:ty) => {
339 impl<M> $imp for &$t
340 where
341 M: MIntBase,
342 {
343 type Output = <$t as $imp>::Output;
344 #[inline]
345 fn $method(self) -> <$t as $imp>::Output {
346 $imp::$method(*self)
347 }
348 }
349 };
350}
351impl_mint_ref_unop!(Neg, neg, MInt<M>);
352macro_rules! impl_mint_ref_op_assign {
353 ($imp:ident, $method:ident, $t:ty, $fromimp:ident, $frommethod:ident) => {
354 impl<M> $imp<$t> for $t
355 where
356 M: MIntBase,
357 {
358 #[inline]
359 fn $method(&mut self, rhs: $t) {
360 *self = $fromimp::$frommethod(*self, rhs);
361 }
362 }
363 impl<M> $imp<&$t> for $t
364 where
365 M: MIntBase,
366 {
367 #[inline]
368 fn $method(&mut self, other: &$t) {
369 $imp::$method(self, *other);
370 }
371 }
372 };
373}
374impl_mint_ref_op_assign!(AddAssign, add_assign, MInt<M>, Add, add);
375impl_mint_ref_op_assign!(SubAssign, sub_assign, MInt<M>, Sub, sub);
376impl_mint_ref_op_assign!(MulAssign, mul_assign, MInt<M>, Mul, mul);
377impl_mint_ref_op_assign!(DivAssign, div_assign, MInt<M>, Div, div);