competitive/num/
integer.rs

1use super::{Bounded, IterScan, One, Zero};
2use std::{
3    convert::TryFrom,
4    fmt::{self, Display},
5    iter::{Product, Sum},
6    ops::{
7        Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div,
8        DivAssign, Mul, MulAssign, Neg, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub,
9        SubAssign,
10    },
11    str::FromStr,
12};
13
14// primitive integer = arithmetic operations + binary represented operation
15// arithmetic operations = integer basic operations + (unsigned operations | signed operations)
16
17/// Trait for basic primitive integer operations.
18pub trait IntBase:
19    Copy
20    + Bounded
21    + Zero
22    + One
23    + Eq
24    + Ord
25    + Default
26    + FromStr
27    + Display
28    + Add<Output = Self>
29    + Sub<Output = Self>
30    + Mul<Output = Self>
31    + Div<Output = Self>
32    + Rem<Output = Self>
33    + AddAssign
34    + SubAssign
35    + MulAssign
36    + DivAssign
37    + RemAssign
38    + Sum
39    + Product
40{
41    type Error;
42    fn div_euclid(self, rhs: Self) -> Self;
43    fn rem_euclid(self, rhs: Self) -> Self;
44    fn pow(self, exp: u32) -> Self;
45    fn from_str_radix(src: &str, radix: u32) -> Result<Self, Self::Error>;
46    fn ilog(self, base: Self) -> u32;
47    fn ilog2(self) -> u32;
48    fn ilog10(self) -> u32;
49}
50macro_rules! impl_int_base {
51    ($($t:ty)*) => {
52        $(
53            impl IntBase for $t {
54                type Error = std::num::ParseIntError;
55                fn div_euclid(self, rhs: Self) -> Self { self.div_euclid(rhs) }
56                fn rem_euclid(self, rhs: Self) -> Self { self.rem_euclid(rhs) }
57                fn pow(self, exp: u32) -> Self { self.pow(exp) }
58                fn from_str_radix(src: &str, radix: u32) -> Result<Self, Self::Error> { Self::from_str_radix(src, radix) }
59                fn ilog(self, base: Self) -> u32 { self.ilog(base) }
60                fn ilog2(self) -> u32 { self.ilog2() }
61                fn ilog10(self) -> u32 { self.ilog10() }
62            }
63        )*
64    };
65}
66impl_int_base!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
67
68/// extended_gcd(a,b): ax + by = g = gcd(a,b)
69pub struct ExtendedGcd<T: Unsigned> {
70    /// gcd
71    pub g: T,
72    pub x: T::Signed,
73    pub y: T::Signed,
74}
75
76/// Trait for unsigned integer operations.
77pub trait Unsigned: IntBase {
78    type Signed: Signed<Unsigned = Self>;
79    fn signed(self) -> Self::Signed;
80    fn abs_diff(self, other: Self) -> Self;
81    fn next_power_of_two(self) -> Self;
82    fn gcd(self, other: Self) -> Self;
83    fn lcm(self, other: Self) -> Self {
84        if self.is_zero() && other.is_zero() {
85            Self::zero()
86        } else {
87            self / self.gcd(other) * other
88        }
89    }
90    fn extgcd(self, other: Self) -> ExtendedGcd<Self> {
91        let (mut a, mut b) = (self.signed(), other.signed());
92        let (mut u, mut v, mut x, mut y) = (
93            Self::Signed::one(),
94            Self::Signed::zero(),
95            Self::Signed::zero(),
96            Self::Signed::one(),
97        );
98        while !a.is_zero() {
99            let k = b / a;
100            x -= k * u;
101            y -= k * v;
102            b -= k * a;
103            std::mem::swap(&mut x, &mut u);
104            std::mem::swap(&mut y, &mut v);
105            std::mem::swap(&mut b, &mut a);
106        }
107        ExtendedGcd {
108            g: b.unsigned(),
109            x,
110            y,
111        }
112    }
113    fn modinv(self, modulo: Self) -> Self {
114        assert!(
115            !self.is_zero(),
116            "attempt to inverse zero with modulo {}",
117            modulo
118        );
119        let extgcd = self.extgcd(modulo);
120        assert!(
121            extgcd.g.is_one(),
122            "there is no inverse {} modulo {}",
123            self,
124            modulo
125        );
126        extgcd.x.rem_euclid(modulo.signed()).unsigned()
127    }
128}
129/// Trait for signed integer operations.
130pub trait Signed: IntBase + Neg<Output = Self> {
131    type Unsigned: Unsigned<Signed = Self>;
132    fn unsigned(self) -> Self::Unsigned;
133    fn abs(self) -> Self;
134    fn abs_diff(self, other: Self) -> Self::Unsigned;
135    fn is_negative(self) -> bool;
136    fn is_positive(self) -> bool;
137    fn signum(self) -> Self;
138}
139
140macro_rules! impl_unsigned_signed {
141    ($($unsigned:ident $signed:ident)*) => {
142        $(
143            impl Unsigned for $unsigned {
144                type Signed = $signed;
145                fn signed(self) -> Self::Signed { self as Self::Signed }
146                fn abs_diff(self, other: Self) -> Self { self.abs_diff(other) }
147                fn next_power_of_two(self) -> Self { self.next_power_of_two() }
148                fn gcd(self, other: Self) -> Self {
149                    let (mut a, mut b) = (self, other);
150                    if a.is_zero() || b.is_zero() {
151                        return a | b;
152                    }
153                    let u = a.trailing_zeros();
154                    let v = b.trailing_zeros();
155                    a >>= u;
156                    b >>= v;
157                    let k = u.min(v);
158                    while a != b {
159                        if a < b {
160                            std::mem::swap(&mut a, &mut b);
161                        }
162                        a -= b;
163                        a >>= a.trailing_zeros();
164                    }
165                    a << k
166                }
167            }
168            impl Signed for $signed {
169                type Unsigned = $unsigned;
170                fn unsigned(self) -> Self::Unsigned { self as Self::Unsigned }
171                fn abs_diff(self, other: Self) -> Self::Unsigned { self.abs_diff(other) }
172                fn abs(self) -> Self { self.abs() }
173                fn is_negative(self) -> bool { self.is_negative() }
174                fn is_positive(self) -> bool { self.is_positive() }
175                fn signum(self) -> Self { self.signum() }
176            }
177        )*
178    };
179}
180impl_unsigned_signed!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
181
182/// Trait for operations of integer in binary representation.
183pub trait BinaryRepr<Size = u32>:
184    Sized
185    + Not<Output = Self>
186    + BitAnd<Output = Self>
187    + BitOr<Output = Self>
188    + BitXor<Output = Self>
189    + Shl<Size, Output = Self>
190    + Shr<Size, Output = Self>
191    + BitAndAssign
192    + BitOrAssign
193    + BitXorAssign
194    + ShlAssign<Size>
195    + ShrAssign<Size>
196{
197    fn count_ones(self) -> Size;
198    fn count_zeros(self) -> Size;
199    fn leading_ones(self) -> Size;
200    fn leading_zeros(self) -> Size;
201    fn reverse_bits(self) -> Self;
202    fn rotate_left(self, n: Size) -> Self;
203    fn rotate_right(self, n: Size) -> Self;
204    fn swap_bytes(self) -> Self;
205    fn trailing_ones(self) -> Size;
206    fn trailing_zeros(self) -> Size;
207}
208
209macro_rules! impl_binary_repr {
210    ($($t:ty)*) => {
211        $(
212            impl BinaryRepr for $t {
213                fn count_ones(self) -> u32 { self.count_ones() }
214                fn count_zeros(self) -> u32 { self.count_zeros() }
215                fn leading_ones(self) -> u32 { self.leading_ones() }
216                fn leading_zeros(self) -> u32 { self.leading_zeros() }
217                fn reverse_bits(self) -> Self { self.reverse_bits() }
218                fn rotate_left(self, n: u32) -> Self { self.rotate_left(n) }
219                fn rotate_right(self, n: u32) -> Self { self.rotate_right(n) }
220                fn swap_bytes(self) -> Self { self.swap_bytes() }
221                fn trailing_ones(self) -> u32 { self.trailing_ones() }
222                fn trailing_zeros(self) -> u32 { self.trailing_zeros() }
223            }
224        )*
225    };
226}
227impl_binary_repr!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
228
229macro_rules! impl_binop {
230    (impl<$T:ident> $Trait:ident $impl:ident for $t:ty) => {
231        impl<$T> $Trait for $t
232        where
233            $T: $Trait<Output = $T>,
234        {
235            type Output = Self;
236            fn $impl(self, rhs: Self) -> Self::Output {
237                Self($Trait::$impl(self.0, rhs.0))
238            }
239        }
240        impl<$T> $Trait<$T> for $t
241        where
242            $T: $Trait<Output = $T>,
243        {
244            type Output = Self;
245            fn $impl(self, rhs: $T) -> Self::Output {
246                Self($Trait::$impl(self.0, rhs))
247            }
248        }
249    };
250}
251macro_rules! impl_opassign {
252    (impl<$T:ident> $Trait:ident $impl:ident for $t:ty) => {
253        impl<$T> $Trait for $t
254        where
255            $T: $Trait,
256        {
257            fn $impl(&mut self, rhs: Self) {
258                $Trait::$impl(&mut self.0, rhs.0)
259            }
260        }
261        impl<$T> $Trait<$T> for $t
262        where
263            $T: $Trait,
264        {
265            fn $impl(&mut self, rhs: $T) {
266                $Trait::$impl(&mut self.0, rhs)
267            }
268        }
269    };
270    (impl<$T:ident> $Trait:ident $impl:ident for $t:ty => $F:ident $f:ident) => {
271        impl<$T> $Trait for $t
272        where
273            $t: $F<Output = $t> + Copy,
274        {
275            fn $impl(&mut self, rhs: Self) {
276                *self = $F::$f(*self, rhs);
277            }
278        }
279        impl<$T> $Trait<$T> for $t
280        where
281            $t: $F<$T, Output = $t> + Copy,
282        {
283            fn $impl(&mut self, rhs: $T) {
284                *self = $F::$f(*self, rhs);
285            }
286        }
287    };
288}
289
290#[derive(Default, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
291#[repr(transparent)]
292/// Wrapper type of arithmetic `saturating_*` operations.
293pub struct Saturating<T>(pub T);
294pub trait Saturatingable: Sized
295where
296    Saturating<Self>: Copy
297        + Bounded
298        + Zero
299        + One
300        + Eq
301        + Ord
302        + Default
303        + FromStr
304        + Display
305        + Add<Output = Saturating<Self>>
306        + Sub<Output = Saturating<Self>>
307        + Mul<Output = Saturating<Self>>
308        + Div<Output = Saturating<Self>>
309        + Rem<Output = Saturating<Self>>
310        + BitAnd<Output = Saturating<Self>>
311        + BitOr<Output = Saturating<Self>>
312        + BitXor<Output = Saturating<Self>>
313        + Shl<u32, Output = Saturating<Self>>
314        + Shr<u32, Output = Saturating<Self>>
315        + AddAssign
316        + SubAssign
317        + MulAssign
318        + DivAssign
319        + RemAssign
320        + BitAndAssign
321        + BitOrAssign
322        + BitXorAssign
323        + ShlAssign<u32>
324        + ShrAssign<u32>
325        + Not<Output = Saturating<Self>>
326        + Add<Self, Output = Saturating<Self>>
327        + Sub<Self, Output = Saturating<Self>>
328        + Mul<Self, Output = Saturating<Self>>
329        + Div<Self, Output = Saturating<Self>>
330        + Rem<Self, Output = Saturating<Self>>
331        + BitAnd<Self, Output = Saturating<Self>>
332        + BitOr<Self, Output = Saturating<Self>>
333        + BitXor<Self, Output = Saturating<Self>>
334        + AddAssign<Self>
335        + SubAssign<Self>
336        + MulAssign<Self>
337        + DivAssign<Self>
338        + RemAssign<Self>
339        + BitAndAssign<Self>
340        + BitOrAssign<Self>
341        + BitXorAssign<Self>,
342{
343    fn to_saturating(self) -> Saturating<Self> {
344        Saturating(self)
345    }
346    fn from_saturating(s: Saturating<Self>) -> Self {
347        s.0
348    }
349}
350
351impl<T> fmt::Debug for Saturating<T>
352where
353    T: fmt::Debug,
354{
355    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
356        T::fmt(&self.0, f)
357    }
358}
359impl<T> Bounded for Saturating<T>
360where
361    T: Bounded,
362{
363    fn maximum() -> Self {
364        Self(T::maximum())
365    }
366    fn minimum() -> Self {
367        Self(T::minimum())
368    }
369}
370impl<T> Zero for Saturating<T>
371where
372    T: Zero,
373{
374    fn zero() -> Self {
375        Self(T::zero())
376    }
377}
378impl<T> One for Saturating<T>
379where
380    T: One,
381{
382    fn one() -> Self {
383        Self(T::one())
384    }
385}
386impl<T> FromStr for Saturating<T>
387where
388    T: FromStr,
389{
390    type Err = T::Err;
391    fn from_str(s: &str) -> Result<Self, Self::Err> {
392        T::from_str(s).map(Self)
393    }
394}
395impl<T> Display for Saturating<T>
396where
397    T: Display,
398{
399    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
400        T::fmt(&self.0, f)
401    }
402}
403impl<T> IterScan for Saturating<T>
404where
405    T: IterScan<Output = T>,
406{
407    type Output = Self;
408    fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
409        T::scan(iter).map(Self)
410    }
411}
412impl_binop!(impl<T> Div div for Saturating<T>);
413impl_binop!(impl<T> Rem rem for Saturating<T>);
414impl_binop!(impl<T> BitAnd bitand for Saturating<T>);
415impl_binop!(impl<T> BitOr bitor for Saturating<T>);
416impl_binop!(impl<T> BitXor bitxor for Saturating<T>);
417impl_opassign!(impl<T> AddAssign add_assign for Saturating<T> => Add add);
418impl_opassign!(impl<T> SubAssign sub_assign for Saturating<T> => Sub sub);
419impl_opassign!(impl<T> MulAssign mul_assign for Saturating<T> => Mul mul);
420impl_opassign!(impl<T> DivAssign div_assign for Saturating<T>);
421impl_opassign!(impl<T> RemAssign rem_assign for Saturating<T>);
422impl_opassign!(impl<T> BitAndAssign bitand_assign for Saturating<T>);
423impl_opassign!(impl<T> BitOrAssign bitor_assign for Saturating<T>);
424impl_opassign!(impl<T> BitXorAssign bitxor_assign for Saturating<T>);
425impl<T> Not for Saturating<T>
426where
427    T: Not<Output = T>,
428{
429    type Output = Self;
430    fn not(self) -> Self::Output {
431        Self(Not::not(self.0))
432    }
433}
434
435macro_rules! impl_int_base_for_saturating {
436    ($($t:ty)*) => {
437        $(
438            impl Saturatingable for $t {}
439            impl Add for Saturating<$t> {
440                type Output = Self;
441                fn add(self, rhs: Self) -> Self::Output {
442                    Self(self.0.saturating_add(rhs.0))
443                }
444            }
445            impl Add<$t> for Saturating<$t> {
446                type Output = Self;
447                fn add(self, rhs: $t) -> Self::Output {
448                    Self(self.0.saturating_add(rhs))
449                }
450            }
451            impl Sub for Saturating<$t> {
452                type Output = Self;
453                fn sub(self, rhs: Self) -> Self::Output {
454                    Self(self.0.saturating_sub(rhs.0))
455                }
456            }
457            impl Sub<$t> for Saturating<$t> {
458                type Output = Self;
459                fn sub(self, rhs: $t) -> Self::Output {
460                    Self(self.0.saturating_sub(rhs))
461                }
462            }
463            impl Mul for Saturating<$t> {
464                type Output = Self;
465                fn mul(self, rhs: Self) -> Self::Output {
466                    Self(self.0.saturating_mul(rhs.0))
467                }
468            }
469            impl Mul<$t> for Saturating<$t> {
470                type Output = Self;
471                fn mul(self, rhs: $t) -> Self::Output {
472                    Self(self.0.saturating_mul(rhs))
473                }
474            }
475            impl Sum for Saturating<$t> {
476                fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
477                    iter.fold(Self::zero(), |acc, x| acc + x)
478                }
479            }
480            impl Product for Saturating<$t> {
481                fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
482                    iter.fold(Self::one(), |acc, x| acc * x)
483                }
484            }
485            impl IntBase for Saturating<$t> {
486                type Error = <$t as IntBase>::Error;
487                fn div_euclid(self, rhs: Self) -> Self { Self(self.0.div_euclid(rhs.0)) }
488                fn rem_euclid(self, rhs: Self) -> Self { Self(self.0.rem_euclid(rhs.0)) }
489                fn pow(self, exp: u32) -> Self { Self(self.0.saturating_pow(exp)) }
490                fn from_str_radix(src: &str, radix: u32) -> Result<Self, Self::Error> { <$t as IntBase>::from_str_radix(src, radix).map(Self) }
491                fn ilog(self, base: Self) -> u32 { self.0.ilog(base.0) }
492                fn ilog2(self) -> u32 { self.0.ilog2() }
493                fn ilog10(self) -> u32 { self.0.ilog10() }
494            }
495            impl From<$t> for Saturating<$t> {
496                fn from(t: $t) -> Self {
497                    Self(t)
498                }
499            }
500        )*
501    };
502}
503impl_int_base_for_saturating!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
504
505macro_rules! impl_unsigned_signed_for_saturating {
506    ($($unsigned:ident $signed:ident)*) => {
507        $(
508            impl Unsigned for Saturating<$unsigned> {
509                type Signed = Saturating<$signed>;
510                fn signed(self) -> Self::Signed { Saturating(TryFrom::try_from(self.0).ok().unwrap_or_else($signed::maximum)) }
511                fn abs_diff(self, other: Self) -> Self { Self(self.0.abs_diff(other.0)) }
512                fn next_power_of_two(self) -> Self { Self(self.0.next_power_of_two()) }
513                fn gcd(self, other: Self) -> Self { Self(self.0.gcd(other.0)) }
514            }
515            impl Signed for Saturating<$signed> {
516                type Unsigned = Saturating<$unsigned>;
517                fn unsigned(self) -> Self::Unsigned { Saturating(TryFrom::try_from(self.0).ok().unwrap_or_else($unsigned::minimum)) }
518                fn abs(self) -> Self { Self(self.0.saturating_abs()) }
519                fn abs_diff(self, other: Self) -> Self::Unsigned { Saturating(self.0.abs_diff(other.0)) }
520                fn is_negative(self) -> bool { self.0.is_negative() }
521                fn is_positive(self) -> bool { self.0.is_positive() }
522                fn signum(self) -> Self { Self(self.0.signum()) }
523            }
524            impl Neg for Saturating<$signed> {
525                type Output = Self;
526                fn neg(self) -> Self::Output {
527                    Self(self.0.saturating_neg())
528                }
529            }
530        )*
531    };
532}
533impl_unsigned_signed_for_saturating!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
534
535macro_rules! impl_binary_repr_for_saturating {
536    ($($t:ty)*) => {
537        $(
538            impl Shl<u32> for Saturating<$t> {
539                type Output = Self;
540                fn shl(self, rhs: u32) -> Self::Output {
541                    Self(self.0.checked_shl(rhs).unwrap_or(0))
542                }
543            }
544            impl Shr<u32> for Saturating<$t> {
545                type Output = Self;
546                fn shr(self, rhs: u32) -> Self::Output {
547                    Self(self.0.checked_shr(rhs).unwrap_or(0))
548                }
549            }
550            impl ShlAssign<u32> for Saturating<$t> {
551                fn shl_assign(&mut self, rhs: u32) {
552                    *self = Shl::shl(*self, rhs);
553                }
554            }
555            impl ShrAssign<u32> for Saturating<$t> {
556                fn shr_assign(&mut self, rhs: u32) {
557                    *self = Shr::shr(*self, rhs);
558                }
559            }
560            impl BinaryRepr for Saturating<$t> {
561                fn count_ones(self) -> u32 { self.0.count_ones() }
562                fn count_zeros(self) -> u32 { self.0.count_zeros() }
563                fn leading_ones(self) -> u32 { self.0.leading_ones() }
564                fn leading_zeros(self) -> u32 { self.0.leading_zeros() }
565                fn reverse_bits(self) -> Self { Self(self.0.reverse_bits()) }
566                fn rotate_left(self, n: u32) -> Self { Self(self.0.rotate_left(n)) }
567                fn rotate_right(self, n: u32) -> Self { Self(self.0.rotate_right(n)) }
568                fn swap_bytes(self) -> Self { Self(self.0.swap_bytes()) }
569                fn trailing_ones(self) -> u32 { self.0.trailing_ones() }
570                fn trailing_zeros(self) -> u32 { self.0.trailing_zeros() }
571            }
572        )*
573    };
574}
575impl_binary_repr_for_saturating!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
576
577#[derive(Default, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
578#[repr(transparent)]
579/// Wrapper type of arithmetic `wrapping_*` operations.
580pub struct Wrapping<T>(pub T);
581pub trait Wrappingable: Sized
582where
583    Wrapping<Self>: Copy
584        + Bounded
585        + Zero
586        + One
587        + Eq
588        + Ord
589        + Default
590        + FromStr
591        + Display
592        + Add<Output = Wrapping<Self>>
593        + Sub<Output = Wrapping<Self>>
594        + Mul<Output = Wrapping<Self>>
595        + Div<Output = Wrapping<Self>>
596        + Rem<Output = Wrapping<Self>>
597        + BitAnd<Output = Wrapping<Self>>
598        + BitOr<Output = Wrapping<Self>>
599        + BitXor<Output = Wrapping<Self>>
600        + Shl<u32, Output = Wrapping<Self>>
601        + Shr<u32, Output = Wrapping<Self>>
602        + AddAssign
603        + SubAssign
604        + MulAssign
605        + DivAssign
606        + RemAssign
607        + BitAndAssign
608        + BitOrAssign
609        + BitXorAssign
610        + ShlAssign<u32>
611        + ShrAssign<u32>
612        + Not<Output = Wrapping<Self>>
613        + Add<Self, Output = Wrapping<Self>>
614        + Sub<Self, Output = Wrapping<Self>>
615        + Mul<Self, Output = Wrapping<Self>>
616        + Div<Self, Output = Wrapping<Self>>
617        + Rem<Self, Output = Wrapping<Self>>
618        + BitAnd<Self, Output = Wrapping<Self>>
619        + BitOr<Self, Output = Wrapping<Self>>
620        + BitXor<Self, Output = Wrapping<Self>>
621        + AddAssign<Self>
622        + SubAssign<Self>
623        + MulAssign<Self>
624        + DivAssign<Self>
625        + RemAssign<Self>
626        + BitAndAssign<Self>
627        + BitOrAssign<Self>
628        + BitXorAssign<Self>,
629{
630    fn to_wrapping(self) -> Wrapping<Self> {
631        Wrapping(self)
632    }
633    fn from_wrapping(w: Wrapping<Self>) -> Self {
634        w.0
635    }
636}
637
638impl<T> fmt::Debug for Wrapping<T>
639where
640    T: fmt::Debug,
641{
642    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
643        T::fmt(&self.0, f)
644    }
645}
646impl<T> Bounded for Wrapping<T>
647where
648    T: Bounded,
649{
650    fn maximum() -> Self {
651        Self(T::maximum())
652    }
653    fn minimum() -> Self {
654        Self(T::minimum())
655    }
656}
657impl<T> Zero for Wrapping<T>
658where
659    T: Zero,
660{
661    fn zero() -> Self {
662        Self(T::zero())
663    }
664}
665impl<T> One for Wrapping<T>
666where
667    T: One,
668{
669    fn one() -> Self {
670        Self(T::one())
671    }
672}
673impl<T> FromStr for Wrapping<T>
674where
675    T: FromStr,
676{
677    type Err = T::Err;
678    fn from_str(s: &str) -> Result<Self, Self::Err> {
679        T::from_str(s).map(Self)
680    }
681}
682impl<T> Display for Wrapping<T>
683where
684    T: Display,
685{
686    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
687        T::fmt(&self.0, f)
688    }
689}
690impl<T> IterScan for Wrapping<T>
691where
692    T: IterScan<Output = T>,
693{
694    type Output = Self;
695    fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
696        T::scan(iter).map(Self)
697    }
698}
699impl_binop!(impl<T> BitAnd bitand for Wrapping<T>);
700impl_binop!(impl<T> BitOr bitor for Wrapping<T>);
701impl_binop!(impl<T> BitXor bitxor for Wrapping<T>);
702impl_opassign!(impl<T> AddAssign add_assign for Wrapping<T> => Add add);
703impl_opassign!(impl<T> SubAssign sub_assign for Wrapping<T> => Sub sub);
704impl_opassign!(impl<T> MulAssign mul_assign for Wrapping<T> => Mul mul);
705impl_opassign!(impl<T> DivAssign div_assign for Wrapping<T> => Div div);
706impl_opassign!(impl<T> RemAssign rem_assign for Wrapping<T> => Rem rem);
707impl_opassign!(impl<T> BitAndAssign bitand_assign for Wrapping<T>);
708impl_opassign!(impl<T> BitOrAssign bitor_assign for Wrapping<T>);
709impl_opassign!(impl<T> BitXorAssign bitxor_assign for Wrapping<T>);
710impl<T> Not for Wrapping<T>
711where
712    T: Not<Output = T>,
713{
714    type Output = Self;
715    fn not(self) -> Self::Output {
716        Self(Not::not(self.0))
717    }
718}
719
720macro_rules! impl_int_base_for_wrapping {
721    ($($t:ty)*) => {
722        $(
723            impl Wrappingable for $t {}
724            impl Add for Wrapping<$t> {
725                type Output = Self;
726                fn add(self, rhs: Self) -> Self::Output {
727                    Self(self.0.wrapping_add(rhs.0))
728                }
729            }
730            impl Add<$t> for Wrapping<$t> {
731                type Output = Self;
732                fn add(self, rhs: $t) -> Self::Output {
733                    Self(self.0.wrapping_add(rhs))
734                }
735            }
736            impl Sub for Wrapping<$t> {
737                type Output = Self;
738                fn sub(self, rhs: Self) -> Self::Output {
739                    Self(self.0.wrapping_sub(rhs.0))
740                }
741            }
742            impl Sub<$t> for Wrapping<$t> {
743                type Output = Self;
744                fn sub(self, rhs: $t) -> Self::Output {
745                    Self(self.0.wrapping_sub(rhs))
746                }
747            }
748            impl Mul for Wrapping<$t> {
749                type Output = Self;
750                fn mul(self, rhs: Self) -> Self::Output {
751                    Self(self.0.wrapping_mul(rhs.0))
752                }
753            }
754            impl Mul<$t> for Wrapping<$t> {
755                type Output = Self;
756                fn mul(self, rhs: $t) -> Self::Output {
757                    Self(self.0.wrapping_mul(rhs))
758                }
759            }
760            impl Div for Wrapping<$t> {
761                type Output = Self;
762                fn div(self, rhs: Self) -> Self::Output {
763                    Self(self.0.wrapping_div(rhs.0))
764                }
765            }
766            impl Div<$t> for Wrapping<$t> {
767                type Output = Self;
768                fn div(self, rhs: $t) -> Self::Output {
769                    Self(self.0.wrapping_div(rhs))
770                }
771            }
772            impl Rem for Wrapping<$t> {
773                type Output = Self;
774                fn rem(self, rhs: Self) -> Self::Output {
775                    Self(self.0.wrapping_rem(rhs.0))
776                }
777            }
778            impl Rem<$t> for Wrapping<$t> {
779                type Output = Self;
780                fn rem(self, rhs: $t) -> Self::Output {
781                    Self(self.0.wrapping_rem(rhs))
782                }
783            }
784            impl Sum for Wrapping<$t> {
785                fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
786                    iter.fold(Self::zero(), |acc, x| acc + x)
787                }
788            }
789            impl Product for Wrapping<$t> {
790                fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
791                    iter.fold(Self::one(), |acc, x| acc * x)
792                }
793            }
794            impl IntBase for Wrapping<$t> {
795                type Error = <$t as IntBase>::Error;
796                fn div_euclid(self, rhs: Self) -> Self { Self(self.0.wrapping_div_euclid(rhs.0)) }
797                fn rem_euclid(self, rhs: Self) -> Self { Self(self.0.wrapping_rem_euclid(rhs.0)) }
798                fn pow(self, exp: u32) -> Self { Self(self.0.wrapping_pow(exp)) }
799                fn from_str_radix(src: &str, radix: u32) -> Result<Self, Self::Error> { <$t as IntBase>::from_str_radix(src, radix).map(Self) }
800                fn ilog(self, base: Self) -> u32 { self.0.ilog(base.0) }
801                fn ilog2(self) -> u32 { self.0.ilog2() }
802                fn ilog10(self) -> u32 { self.0.ilog10() }
803            }
804            impl From<$t> for Wrapping<$t> {
805                fn from(t: $t) -> Self {
806                    Self(t)
807                }
808            }
809        )*
810    };
811}
812impl_int_base_for_wrapping!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
813
814macro_rules! impl_unsigned_signed_for_wrapping {
815    ($($unsigned:ident $signed:ident)*) => {
816        $(
817            impl Unsigned for Wrapping<$unsigned> {
818                type Signed = Wrapping<$signed>;
819                fn signed(self) -> Self::Signed { Wrapping(self.0.signed()) }
820                fn abs_diff(self, other: Self) -> Self { Self(self.0.abs_diff(other.0)) }
821                fn next_power_of_two(self) -> Self { Self(self.0.next_power_of_two()) }
822                fn gcd(self, other: Self) -> Self { Self(self.0.gcd(other.0)) }
823            }
824            impl Signed for Wrapping<$signed> {
825                type Unsigned = Wrapping<$unsigned>;
826                fn unsigned(self) -> Self::Unsigned { Wrapping(self.0.unsigned()) }
827                fn abs(self) -> Self { Self(self.0.wrapping_abs()) }
828                fn abs_diff(self, other: Self) -> Self::Unsigned { Wrapping(self.0.abs_diff(other.0)) }
829                fn is_negative(self) -> bool { self.0.is_negative() }
830                fn is_positive(self) -> bool { self.0.is_positive() }
831                fn signum(self) -> Self { Self(self.0.signum()) }
832            }
833            impl Neg for Wrapping<$signed> {
834                type Output = Self;
835                fn neg(self) -> Self::Output {
836                    Self(self.0.wrapping_neg())
837                }
838            }
839        )*
840    };
841}
842impl_unsigned_signed_for_wrapping!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
843
844macro_rules! impl_binary_repr_for_wrapping {
845    ($($t:ty)*) => {
846        $(
847            impl Shl<u32> for Wrapping<$t> {
848                type Output = Self;
849                fn shl(self, rhs: u32) -> Self::Output {
850                    Self(self.0.wrapping_shl(rhs))
851                }
852            }
853            impl Shr<u32> for Wrapping<$t> {
854                type Output = Self;
855                fn shr(self, rhs: u32) -> Self::Output {
856                    Self(self.0.wrapping_shr(rhs))
857                }
858            }
859            impl ShlAssign<u32> for Wrapping<$t> {
860                fn shl_assign(&mut self, rhs: u32) {
861                    *self = Shl::shl(*self, rhs);
862                }
863            }
864            impl ShrAssign<u32> for Wrapping<$t> {
865                fn shr_assign(&mut self, rhs: u32) {
866                    *self = Shr::shr(*self, rhs);
867                }
868            }
869            impl BinaryRepr for Wrapping<$t> {
870                fn count_ones(self) -> u32 { self.0.count_ones() }
871                fn count_zeros(self) -> u32 { self.0.count_zeros() }
872                fn leading_ones(self) -> u32 { self.0.leading_ones() }
873                fn leading_zeros(self) -> u32 { self.0.leading_zeros() }
874                fn reverse_bits(self) -> Self { Self(self.0.reverse_bits()) }
875                fn rotate_left(self, n: u32) -> Self { Self(self.0.rotate_left(n)) }
876                fn rotate_right(self, n: u32) -> Self { Self(self.0.rotate_right(n)) }
877                fn swap_bytes(self) -> Self { Self(self.0.swap_bytes()) }
878                fn trailing_ones(self) -> u32 { self.0.trailing_ones() }
879                fn trailing_zeros(self) -> u32 { self.0.trailing_zeros() }
880            }
881        )*
882    };
883}
884impl_binary_repr_for_wrapping!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
885
886#[cfg(test)]
887mod tests {
888    use super::*;
889    use crate::tools::Xorshift;
890    const Q: usize = 10_000;
891    macro_rules! test_unsigned {
892        ($($t:ident)*) => {
893            $(
894                mod $t {
895                    use super::*;
896                    const A: $t = $t::MAX / 2;
897                    fn gcd(mut a: $t, mut b: $t) -> $t {
898                        while b != 0 {
899                            a %= b;
900                            std::mem::swap(&mut a, &mut b);
901                        }
902                        a
903                    }
904                    #[test]
905                    fn test_gcd() {
906                        let mut rng = Xorshift::default();
907                            for (a, b) in rng.random_iter((0..=A, 0..=A)).take(Q) {
908                            assert_eq!(a.gcd(b), gcd(a, b));
909                        }
910                        assert_eq!($t::zero().gcd(0), 0);
911                        assert_eq!($t::zero().gcd(100), 100);
912                    }
913                    #[test]
914                    fn test_extgcd() {
915                        let mut rng = Xorshift::default();
916                        for (a, b) in rng.random_iter((0..=A, 0..=A)).take(Q) {
917                            let ExtendedGcd { g, x, y } = a.extgcd(b);
918                            assert_eq!(g, a.gcd(b));
919                            assert_eq!(a as i128 * x as i128 + b as i128 * y as i128, g as i128);
920                        }
921                    }
922                    #[test]
923                    fn test_modinv() {
924                        let mut rng = Xorshift::default();
925                        for _ in 0..Q {
926                            let m = rng.random(2..=A);
927                            let a = rng.random(1..m);
928                            let g = a.gcd(m);
929                            let m = m / g;
930                            let a = a / g;
931                            let x = a.modinv(m);
932                            assert!(x < m);
933                            assert_eq!(a as u128 * x as u128 % m as u128, 1);
934                        }
935                    }
936                }
937            )*
938        };
939    }
940    test_unsigned!(u8 u16 u32 u64 usize);
941}
competitive/num/integer.rs

competitive/num/
integer.rs
