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
14pub 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 fn isqrt(self) -> Self;
50 fn midpoint(self, rhs: Self) -> Self;
51}
52macro_rules! impl_int_base {
53 ($($t:ty)*) => {
54 $(
55 impl IntBase for $t {
56 type Error = std::num::ParseIntError;
57 fn div_euclid(self, rhs: Self) -> Self { self.div_euclid(rhs) }
58 fn rem_euclid(self, rhs: Self) -> Self { self.rem_euclid(rhs) }
59 fn pow(self, exp: u32) -> Self { self.pow(exp) }
60 fn from_str_radix(src: &str, radix: u32) -> Result<Self, Self::Error> { Self::from_str_radix(src, radix) }
61 fn ilog(self, base: Self) -> u32 { self.ilog(base) }
62 fn ilog2(self) -> u32 { self.ilog2() }
63 fn ilog10(self) -> u32 { self.ilog10() }
64 fn isqrt(self) -> Self { self.isqrt() }
65 fn midpoint(self, rhs: Self) -> Self { self.midpoint(rhs) }
66 }
67 )*
68 };
69}
70impl_int_base!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
71
72pub struct ExtendedGcd<T: Signed> {
74 pub g: T::Unsigned,
76 pub x: T,
77 pub y: T,
78}
79
80pub trait Unsigned: IntBase {
82 type Signed: Signed<Unsigned = Self>;
83 fn signed(self) -> Self::Signed;
84 fn abs_diff(self, other: Self) -> Self;
85 fn div_ceil(self, rhs: Self) -> Self;
86 fn is_power_of_two(self) -> bool;
87 fn next_power_of_two(self) -> Self;
88 fn is_multiple_of(self, rhs: Self) -> bool;
89 fn next_multiple_of(self, rhs: Self) -> Self;
90 fn gcd(self, other: Self) -> Self;
91 fn lcm(self, other: Self) -> Self {
92 if self.is_zero() && other.is_zero() {
93 Self::zero()
94 } else {
95 self / self.gcd(other) * other
96 }
97 }
98 fn mod_inv(self, modulo: Self) -> Self {
99 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
100 let extgcd = self.signed().extgcd(modulo.signed());
101 debug_assert!(extgcd.g.is_one(), "not coprime");
102 extgcd.x.rem_euclid(modulo.signed()).unsigned()
103 }
104 fn mod_add(self, rhs: Self, modulo: Self) -> Self;
105 fn mod_sub(self, rhs: Self, modulo: Self) -> Self;
106 fn mod_mul(self, rhs: Self, modulo: Self) -> Self;
107 fn mod_neg(self, modulo: Self) -> Self {
108 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
109 debug_assert!(self < modulo, "self must be less than modulo");
110 if self.is_zero() {
111 Self::zero()
112 } else {
113 modulo - self
114 }
115 }
116}
117
118pub trait Signed: IntBase + Neg<Output = Self> {
120 type Unsigned: Unsigned<Signed = Self>;
121 fn unsigned(self) -> Self::Unsigned;
122 fn abs(self) -> Self;
123 fn abs_diff(self, other: Self) -> Self::Unsigned;
124 fn is_negative(self) -> bool;
125 fn is_positive(self) -> bool;
126 fn signum(self) -> Self;
127 fn extgcd(self, other: Self) -> ExtendedGcd<Self> {
128 let (mut a, mut b) = (self, other);
129 let (mut u, mut v, mut x, mut y) = (Self::one(), Self::zero(), Self::zero(), Self::one());
130 while !a.is_zero() {
131 let k = b / a;
132 x -= k * u;
133 y -= k * v;
134 b -= k * a;
135 std::mem::swap(&mut x, &mut u);
136 std::mem::swap(&mut y, &mut v);
137 std::mem::swap(&mut b, &mut a);
138 }
139 if b.is_negative() {
140 b = -b;
141 x = -x;
142 y = -y;
143 }
144 ExtendedGcd {
145 g: b.unsigned(),
146 x,
147 y,
148 }
149 }
150}
151
152macro_rules! impl_unsigned_signed {
153 ($([$($tt:tt)*])*) => {
154 $(impl_unsigned_signed!($($tt)*);)*
155 };
156 ($unsigned:ident $signed:ident $upperty:ident) => {
157 impl_unsigned_signed!(
158 @inner $unsigned $signed
159 fn mod_mul(self, rhs: Self, modulo: Self) -> Self {
160 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
161 (self as $upperty * rhs as $upperty % modulo as $upperty) as $unsigned
162 }
163 );
164 };
165 (u128 i128) => {
166 impl_unsigned_signed!(
167 @inner u128 i128
168 fn mod_mul(self, rhs: Self, modulo: Self) -> Self {
169 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
170 const MASK64: u128 = 0xffff_ffff_ffff_ffff;
171 let (au, ad) = (self >> 64, self & MASK64);
172 let (bu, bd) = (rhs >> 64, rhs & MASK64);
173 let p0 = ad * bd % modulo;
174 let p2 = au * bu % modulo;
175 let mut x = [
176 p0 as u64,
177 (p0 >> 64) as u64,
178 p2 as u64,
179 (p2 >> 64) as u64,
180 ];
181 let p1 = (au * bd % modulo).mod_add(ad * bu % modulo, modulo);
182 let (p1_lo, p1_hi) = ((p1 & MASK64) as u64, (p1 >> 64) as u64);
183 let (s1, c1) = x[1].overflowing_add(p1_lo);
184 x[1] = s1 as u64;
185 let (s2, c2) = x[2].overflowing_add(p1_hi + c1 as u64);
186 x[2] = s2 as u64;
187 let (s3, _) = x[3].overflowing_add(c2 as u64);
188 x[3] = s3 as u64;
189 rem_u256_by_u128(x, modulo)
190 }
191 );
192 };
193 (@inner $unsigned:ident $signed:ident $mod_mul:item) => {
194 impl Unsigned for $unsigned {
195 type Signed = $signed;
196 fn signed(self) -> Self::Signed { self as Self::Signed }
197 fn abs_diff(self, other: Self) -> Self { self.abs_diff(other) }
198 fn div_ceil(self, rhs: Self) -> Self { self.div_ceil(rhs) }
199 fn is_power_of_two(self) -> bool { self.is_power_of_two() }
200 fn next_power_of_two(self) -> Self { self.next_power_of_two() }
201 fn is_multiple_of(self, rhs: Self) -> bool { self.is_multiple_of(rhs) }
202 fn next_multiple_of(self, rhs: Self) -> Self { self.next_multiple_of(rhs) }
203 fn gcd(self, other: Self) -> Self {
204 let (mut a, mut b) = (self, other);
205 if a.is_zero() || b.is_zero() {
206 return a | b;
207 }
208 let u = a.trailing_zeros();
209 let v = b.trailing_zeros();
210 a >>= u;
211 b >>= v;
212 let k = u.min(v);
213 while a != b {
214 if a < b {
215 std::mem::swap(&mut a, &mut b);
216 }
217 a -= b;
218 a >>= a.trailing_zeros();
219 }
220 a << k
221 }
222 fn mod_add(self, rhs: Self, modulo: Self) -> Self {
223 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
224 debug_assert!(self < modulo, "self must be less than modulo");
225 debug_assert!(rhs < modulo, "rhs must be less than modulo");
226 let s = self.wrapping_add(rhs);
227 if (s < self) || (s >= modulo) { s.wrapping_sub(modulo) } else { s }
228 }
229 fn mod_sub(self, rhs: Self, modulo: Self) -> Self {
230 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
231 debug_assert!(self < modulo, "self must be less than modulo");
232 debug_assert!(rhs < modulo, "rhs must be less than modulo");
233 let d = self.wrapping_sub(rhs);
234 if self < rhs { d.wrapping_add(modulo) } else { d }
235 }
236 $mod_mul
237 }
238 impl Signed for $signed {
239 type Unsigned = $unsigned;
240 fn unsigned(self) -> Self::Unsigned { self as Self::Unsigned }
241 fn abs_diff(self, other: Self) -> Self::Unsigned { self.abs_diff(other) }
242 fn abs(self) -> Self { self.abs() }
243 fn is_negative(self) -> bool { self.is_negative() }
244 fn is_positive(self) -> bool { self.is_positive() }
245 fn signum(self) -> Self { self.signum() }
246 }
247 };
248}
249impl_unsigned_signed!([u8 i8 u16] [u16 i16 u32] [u32 i32 u64] [u64 i64 u128] [u128 i128] [usize isize u128]);
250
251fn rem_u256_by_u128(u: [u64; 4], v: u128) -> u128 {
252 #[inline(always)]
254 fn sub_with_borrow_u64(lhs: u64, rhs: u64, borrow: bool) -> (u64, bool) {
255 let (res, overflow) = lhs.overflowing_sub(rhs);
256 if borrow {
257 let (res, overflow_borrow) = res.overflowing_sub(1);
258 (res, overflow | overflow_borrow)
259 } else {
260 (res, overflow)
261 }
262 }
263
264 debug_assert!(v != 0);
265 let v_hi = (v >> 64) as u64;
266 if v_hi == 0 {
267 let d = v as u64 as u128;
268 let mut rem: u128 = 0;
269 for &w in u.iter().rev() {
270 rem = (rem << 64 | w as u128) % d;
271 }
272 return rem;
273 }
274
275 let v_lo = v as u64;
276 let v_shift = v_hi.leading_zeros();
277 let (vn1, vn0) = if v_shift == 0 {
278 (v_hi, v_lo)
279 } else {
280 let hi = v_hi << v_shift | v_lo >> (64 - v_shift);
281 let lo = v_lo << v_shift;
282 (hi, lo)
283 };
284
285 let mut un = [0u64; 5];
286 if v_shift == 0 {
287 un[0] = u[0];
288 un[1] = u[1];
289 un[2] = u[2];
290 un[3] = u[3];
291 } else {
292 un[0] = u[0] << v_shift;
293 un[1] = u[1] << v_shift | u[0] >> (64 - v_shift);
294 un[2] = u[2] << v_shift | u[1] >> (64 - v_shift);
295 un[3] = u[3] << v_shift | u[2] >> (64 - v_shift);
296 un[4] = u[3] >> (64 - v_shift);
297 }
298
299 for j in (0..=2).rev() {
300 let num = (un[j + 2] as u128) << 64 | un[j + 1] as u128;
301 let (mut qhat, mut rhat) = {
302 let d = vn1 as u128;
303 let q = (num / d).min(u64::MAX as u128);
304 (q as u64, (num - q * d).min(u64::MAX as u128) as u64)
305 };
306 while qhat as u128 * vn0 as u128 > (rhat as u128) << 64 | un[j] as u128 {
307 qhat -= 1;
308 let t = rhat as u128 + vn1 as u128;
309 if t >= 1u128 << 64 {
310 break;
311 }
312 rhat = t as u64;
313 }
314
315 let p0 = qhat as u128 * vn0 as u128;
316 let p1 = qhat as u128 * vn1 as u128;
317 let (p0_hi, p0_lo) = ((p0 >> 64) as u64, p0 as u64);
318 let (p1_hi, p1_lo) = ((p1 >> 64) as u64, p1 as u64);
319
320 let (r0, borrow) = sub_with_borrow_u64(un[j], p0_lo, false);
321 un[j] = r0;
322
323 let (r1, borrow1) = sub_with_borrow_u64(un[j + 1], p0_hi, borrow);
324 let (r1, borrow2) = sub_with_borrow_u64(r1, p1_lo, false);
325 let borrow = borrow1 || borrow2;
326 un[j + 1] = r1;
327
328 let (r2, borrow) = sub_with_borrow_u64(un[j + 2], p1_hi, borrow);
329 un[j + 2] = r2;
330 assert!(!borrow);
331 }
332
333 ((un[1] as u128) << 64 | un[0] as u128) >> v_hi.leading_zeros()
334}
335
336pub trait BinaryRepr<Size = u32>:
338 Sized
339 + Not<Output = Self>
340 + BitAnd<Output = Self>
341 + BitOr<Output = Self>
342 + BitXor<Output = Self>
343 + Shl<Size, Output = Self>
344 + Shr<Size, Output = Self>
345 + BitAndAssign
346 + BitOrAssign
347 + BitXorAssign
348 + ShlAssign<Size>
349 + ShrAssign<Size>
350{
351 fn count_ones(self) -> Size;
352 fn count_zeros(self) -> Size;
353 fn leading_ones(self) -> Size;
354 fn leading_zeros(self) -> Size;
355 fn reverse_bits(self) -> Self;
356 fn rotate_left(self, n: Size) -> Self;
357 fn rotate_right(self, n: Size) -> Self;
358 fn swap_bytes(self) -> Self;
359 fn trailing_ones(self) -> Size;
360 fn trailing_zeros(self) -> Size;
361}
362
363macro_rules! impl_binary_repr {
364 ($($t:ty)*) => {
365 $(
366 impl BinaryRepr for $t {
367 fn count_ones(self) -> u32 { self.count_ones() }
368 fn count_zeros(self) -> u32 { self.count_zeros() }
369 fn leading_ones(self) -> u32 { self.leading_ones() }
370 fn leading_zeros(self) -> u32 { self.leading_zeros() }
371 fn reverse_bits(self) -> Self { self.reverse_bits() }
372 fn rotate_left(self, n: u32) -> Self { self.rotate_left(n) }
373 fn rotate_right(self, n: u32) -> Self { self.rotate_right(n) }
374 fn swap_bytes(self) -> Self { self.swap_bytes() }
375 fn trailing_ones(self) -> u32 { self.trailing_ones() }
376 fn trailing_zeros(self) -> u32 { self.trailing_zeros() }
377 }
378 )*
379 };
380}
381impl_binary_repr!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
382
383macro_rules! impl_binop {
384 (impl<$T:ident> $Trait:ident $impl:ident for $t:ty) => {
385 impl<$T> $Trait for $t
386 where
387 $T: $Trait<Output = $T>,
388 {
389 type Output = Self;
390 fn $impl(self, rhs: Self) -> Self::Output {
391 Self($Trait::$impl(self.0, rhs.0))
392 }
393 }
394 impl<$T> $Trait<$T> for $t
395 where
396 $T: $Trait<Output = $T>,
397 {
398 type Output = Self;
399 fn $impl(self, rhs: $T) -> Self::Output {
400 Self($Trait::$impl(self.0, rhs))
401 }
402 }
403 };
404}
405macro_rules! impl_opassign {
406 (impl<$T:ident> $Trait:ident $impl:ident for $t:ty) => {
407 impl<$T> $Trait for $t
408 where
409 $T: $Trait,
410 {
411 fn $impl(&mut self, rhs: Self) {
412 $Trait::$impl(&mut self.0, rhs.0)
413 }
414 }
415 impl<$T> $Trait<$T> for $t
416 where
417 $T: $Trait,
418 {
419 fn $impl(&mut self, rhs: $T) {
420 $Trait::$impl(&mut self.0, rhs)
421 }
422 }
423 };
424 (impl<$T:ident> $Trait:ident $impl:ident for $t:ty => $F:ident $f:ident) => {
425 impl<$T> $Trait for $t
426 where
427 $t: $F<Output = $t> + Copy,
428 {
429 fn $impl(&mut self, rhs: Self) {
430 *self = $F::$f(*self, rhs);
431 }
432 }
433 impl<$T> $Trait<$T> for $t
434 where
435 $t: $F<$T, Output = $t> + Copy,
436 {
437 fn $impl(&mut self, rhs: $T) {
438 *self = $F::$f(*self, rhs);
439 }
440 }
441 };
442}
443
444#[derive(Default, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
445#[repr(transparent)]
446pub struct Saturating<T>(pub T);
448pub trait Saturatingable: Sized
449where
450 Saturating<Self>: Copy
451 + Bounded
452 + Zero
453 + One
454 + Eq
455 + Ord
456 + Default
457 + FromStr
458 + Display
459 + Add<Output = Saturating<Self>>
460 + Sub<Output = Saturating<Self>>
461 + Mul<Output = Saturating<Self>>
462 + Div<Output = Saturating<Self>>
463 + Rem<Output = Saturating<Self>>
464 + BitAnd<Output = Saturating<Self>>
465 + BitOr<Output = Saturating<Self>>
466 + BitXor<Output = Saturating<Self>>
467 + Shl<u32, Output = Saturating<Self>>
468 + Shr<u32, Output = Saturating<Self>>
469 + AddAssign
470 + SubAssign
471 + MulAssign
472 + DivAssign
473 + RemAssign
474 + BitAndAssign
475 + BitOrAssign
476 + BitXorAssign
477 + ShlAssign<u32>
478 + ShrAssign<u32>
479 + Not<Output = Saturating<Self>>
480 + Add<Self, Output = Saturating<Self>>
481 + Sub<Self, Output = Saturating<Self>>
482 + Mul<Self, Output = Saturating<Self>>
483 + Div<Self, Output = Saturating<Self>>
484 + Rem<Self, Output = Saturating<Self>>
485 + BitAnd<Self, Output = Saturating<Self>>
486 + BitOr<Self, Output = Saturating<Self>>
487 + BitXor<Self, Output = Saturating<Self>>
488 + AddAssign<Self>
489 + SubAssign<Self>
490 + MulAssign<Self>
491 + DivAssign<Self>
492 + RemAssign<Self>
493 + BitAndAssign<Self>
494 + BitOrAssign<Self>
495 + BitXorAssign<Self>,
496{
497 fn to_saturating(self) -> Saturating<Self> {
498 Saturating(self)
499 }
500 fn from_saturating(s: Saturating<Self>) -> Self {
501 s.0
502 }
503}
504
505impl<T> fmt::Debug for Saturating<T>
506where
507 T: fmt::Debug,
508{
509 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
510 T::fmt(&self.0, f)
511 }
512}
513impl<T> Bounded for Saturating<T>
514where
515 T: Bounded,
516{
517 fn maximum() -> Self {
518 Self(T::maximum())
519 }
520 fn minimum() -> Self {
521 Self(T::minimum())
522 }
523}
524impl<T> Zero for Saturating<T>
525where
526 T: Zero,
527{
528 fn zero() -> Self {
529 Self(T::zero())
530 }
531}
532impl<T> One for Saturating<T>
533where
534 T: One,
535{
536 fn one() -> Self {
537 Self(T::one())
538 }
539}
540impl<T> FromStr for Saturating<T>
541where
542 T: FromStr,
543{
544 type Err = T::Err;
545 fn from_str(s: &str) -> Result<Self, Self::Err> {
546 T::from_str(s).map(Self)
547 }
548}
549impl<T> Display for Saturating<T>
550where
551 T: Display,
552{
553 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
554 T::fmt(&self.0, f)
555 }
556}
557impl<T> IterScan for Saturating<T>
558where
559 T: IterScan<Output = T>,
560{
561 type Output = Self;
562 fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
563 T::scan(iter).map(Self)
564 }
565}
566impl_binop!(impl<T> Div div for Saturating<T>);
567impl_binop!(impl<T> Rem rem for Saturating<T>);
568impl_binop!(impl<T> BitAnd bitand for Saturating<T>);
569impl_binop!(impl<T> BitOr bitor for Saturating<T>);
570impl_binop!(impl<T> BitXor bitxor for Saturating<T>);
571impl_opassign!(impl<T> AddAssign add_assign for Saturating<T> => Add add);
572impl_opassign!(impl<T> SubAssign sub_assign for Saturating<T> => Sub sub);
573impl_opassign!(impl<T> MulAssign mul_assign for Saturating<T> => Mul mul);
574impl_opassign!(impl<T> DivAssign div_assign for Saturating<T>);
575impl_opassign!(impl<T> RemAssign rem_assign for Saturating<T>);
576impl_opassign!(impl<T> BitAndAssign bitand_assign for Saturating<T>);
577impl_opassign!(impl<T> BitOrAssign bitor_assign for Saturating<T>);
578impl_opassign!(impl<T> BitXorAssign bitxor_assign for Saturating<T>);
579impl<T> Not for Saturating<T>
580where
581 T: Not<Output = T>,
582{
583 type Output = Self;
584 fn not(self) -> Self::Output {
585 Self(Not::not(self.0))
586 }
587}
588
589macro_rules! impl_int_base_for_saturating {
590 ($($t:ty)*) => {
591 $(
592 impl Saturatingable for $t {}
593 impl Add for Saturating<$t> {
594 type Output = Self;
595 fn add(self, rhs: Self) -> Self::Output {
596 Self(self.0.saturating_add(rhs.0))
597 }
598 }
599 impl Add<$t> for Saturating<$t> {
600 type Output = Self;
601 fn add(self, rhs: $t) -> Self::Output {
602 Self(self.0.saturating_add(rhs))
603 }
604 }
605 impl Sub for Saturating<$t> {
606 type Output = Self;
607 fn sub(self, rhs: Self) -> Self::Output {
608 Self(self.0.saturating_sub(rhs.0))
609 }
610 }
611 impl Sub<$t> for Saturating<$t> {
612 type Output = Self;
613 fn sub(self, rhs: $t) -> Self::Output {
614 Self(self.0.saturating_sub(rhs))
615 }
616 }
617 impl Mul for Saturating<$t> {
618 type Output = Self;
619 fn mul(self, rhs: Self) -> Self::Output {
620 Self(self.0.saturating_mul(rhs.0))
621 }
622 }
623 impl Mul<$t> for Saturating<$t> {
624 type Output = Self;
625 fn mul(self, rhs: $t) -> Self::Output {
626 Self(self.0.saturating_mul(rhs))
627 }
628 }
629 impl Sum for Saturating<$t> {
630 fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
631 iter.fold(Self::zero(), |acc, x| acc + x)
632 }
633 }
634 impl Product for Saturating<$t> {
635 fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
636 iter.fold(Self::one(), |acc, x| acc * x)
637 }
638 }
639 impl IntBase for Saturating<$t> {
640 type Error = <$t as IntBase>::Error;
641 fn div_euclid(self, rhs: Self) -> Self { Self(self.0.div_euclid(rhs.0)) }
642 fn rem_euclid(self, rhs: Self) -> Self { Self(self.0.rem_euclid(rhs.0)) }
643 fn pow(self, exp: u32) -> Self { Self(self.0.saturating_pow(exp)) }
644 fn from_str_radix(src: &str, radix: u32) -> Result<Self, Self::Error> { <$t as IntBase>::from_str_radix(src, radix).map(Self) }
645 fn ilog(self, base: Self) -> u32 { self.0.ilog(base.0) }
646 fn ilog2(self) -> u32 { self.0.ilog2() }
647 fn ilog10(self) -> u32 { self.0.ilog10() }
648 fn isqrt(self) -> Self { Self(self.0.isqrt()) }
649 fn midpoint(self, rhs: Self) -> Self { Self(self.0.midpoint(rhs.0)) }
650 }
651 impl From<$t> for Saturating<$t> {
652 fn from(t: $t) -> Self {
653 Self(t)
654 }
655 }
656 )*
657 };
658}
659impl_int_base_for_saturating!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
660
661macro_rules! impl_unsigned_signed_for_saturating {
662 ($($unsigned:ident $signed:ident)*) => {
663 $(
664 impl Unsigned for Saturating<$unsigned> {
665 type Signed = Saturating<$signed>;
666 fn signed(self) -> Self::Signed { Saturating(TryFrom::try_from(self.0).ok().unwrap_or_else($signed::maximum)) }
667 fn abs_diff(self, other: Self) -> Self { Self(self.0.abs_diff(other.0)) }
668 fn div_ceil(self, rhs: Self) -> Self { Self(self.0.div_ceil(rhs.0)) }
669 fn is_power_of_two(self) -> bool { self.0.is_power_of_two() }
670 fn next_power_of_two(self) -> Self { Self(self.0.next_power_of_two()) }
671 fn is_multiple_of(self, rhs: Self) -> bool { self.0.is_multiple_of(rhs.0) }
672 fn next_multiple_of(self, rhs: Self) -> Self { Self(self.0.next_multiple_of(rhs.0)) }
673 fn gcd(self, other: Self) -> Self { Self(self.0.gcd(other.0)) }
674 fn mod_add(self, rhs: Self, modulo: Self) -> Self { Self(self.0.mod_add(rhs.0, modulo.0)) }
675 fn mod_sub(self, rhs: Self, modulo: Self) -> Self { Self(self.0.mod_sub(rhs.0, modulo.0)) }
676 fn mod_mul(self, rhs: Self, modulo: Self) -> Self { Self(self.0.mod_mul(rhs.0, modulo.0)) }
677 }
678 impl Signed for Saturating<$signed> {
679 type Unsigned = Saturating<$unsigned>;
680 fn unsigned(self) -> Self::Unsigned { Saturating(TryFrom::try_from(self.0).ok().unwrap_or_else($unsigned::minimum)) }
681 fn abs(self) -> Self { Self(self.0.saturating_abs()) }
682 fn abs_diff(self, other: Self) -> Self::Unsigned { Saturating(self.0.abs_diff(other.0)) }
683 fn is_negative(self) -> bool { self.0.is_negative() }
684 fn is_positive(self) -> bool { self.0.is_positive() }
685 fn signum(self) -> Self { Self(self.0.signum()) }
686 }
687 impl Neg for Saturating<$signed> {
688 type Output = Self;
689 fn neg(self) -> Self::Output {
690 Self(self.0.saturating_neg())
691 }
692 }
693 )*
694 };
695}
696impl_unsigned_signed_for_saturating!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
697
698macro_rules! impl_binary_repr_for_saturating {
699 ($($t:ty)*) => {
700 $(
701 impl Shl<u32> for Saturating<$t> {
702 type Output = Self;
703 fn shl(self, rhs: u32) -> Self::Output {
704 Self(self.0.checked_shl(rhs).unwrap_or(0))
705 }
706 }
707 impl Shr<u32> for Saturating<$t> {
708 type Output = Self;
709 fn shr(self, rhs: u32) -> Self::Output {
710 Self(self.0.checked_shr(rhs).unwrap_or(0))
711 }
712 }
713 impl ShlAssign<u32> for Saturating<$t> {
714 fn shl_assign(&mut self, rhs: u32) {
715 *self = Shl::shl(*self, rhs);
716 }
717 }
718 impl ShrAssign<u32> for Saturating<$t> {
719 fn shr_assign(&mut self, rhs: u32) {
720 *self = Shr::shr(*self, rhs);
721 }
722 }
723 impl BinaryRepr for Saturating<$t> {
724 fn count_ones(self) -> u32 { self.0.count_ones() }
725 fn count_zeros(self) -> u32 { self.0.count_zeros() }
726 fn leading_ones(self) -> u32 { self.0.leading_ones() }
727 fn leading_zeros(self) -> u32 { self.0.leading_zeros() }
728 fn reverse_bits(self) -> Self { Self(self.0.reverse_bits()) }
729 fn rotate_left(self, n: u32) -> Self { Self(self.0.rotate_left(n)) }
730 fn rotate_right(self, n: u32) -> Self { Self(self.0.rotate_right(n)) }
731 fn swap_bytes(self) -> Self { Self(self.0.swap_bytes()) }
732 fn trailing_ones(self) -> u32 { self.0.trailing_ones() }
733 fn trailing_zeros(self) -> u32 { self.0.trailing_zeros() }
734 }
735 )*
736 };
737}
738impl_binary_repr_for_saturating!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
739
740#[derive(Default, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
741#[repr(transparent)]
742pub struct Wrapping<T>(pub T);
744pub trait Wrappingable: Sized
745where
746 Wrapping<Self>: Copy
747 + Bounded
748 + Zero
749 + One
750 + Eq
751 + Ord
752 + Default
753 + FromStr
754 + Display
755 + Add<Output = Wrapping<Self>>
756 + Sub<Output = Wrapping<Self>>
757 + Mul<Output = Wrapping<Self>>
758 + Div<Output = Wrapping<Self>>
759 + Rem<Output = Wrapping<Self>>
760 + BitAnd<Output = Wrapping<Self>>
761 + BitOr<Output = Wrapping<Self>>
762 + BitXor<Output = Wrapping<Self>>
763 + Shl<u32, Output = Wrapping<Self>>
764 + Shr<u32, Output = Wrapping<Self>>
765 + AddAssign
766 + SubAssign
767 + MulAssign
768 + DivAssign
769 + RemAssign
770 + BitAndAssign
771 + BitOrAssign
772 + BitXorAssign
773 + ShlAssign<u32>
774 + ShrAssign<u32>
775 + Not<Output = Wrapping<Self>>
776 + Add<Self, Output = Wrapping<Self>>
777 + Sub<Self, Output = Wrapping<Self>>
778 + Mul<Self, Output = Wrapping<Self>>
779 + Div<Self, Output = Wrapping<Self>>
780 + Rem<Self, Output = Wrapping<Self>>
781 + BitAnd<Self, Output = Wrapping<Self>>
782 + BitOr<Self, Output = Wrapping<Self>>
783 + BitXor<Self, Output = Wrapping<Self>>
784 + AddAssign<Self>
785 + SubAssign<Self>
786 + MulAssign<Self>
787 + DivAssign<Self>
788 + RemAssign<Self>
789 + BitAndAssign<Self>
790 + BitOrAssign<Self>
791 + BitXorAssign<Self>,
792{
793 fn to_wrapping(self) -> Wrapping<Self> {
794 Wrapping(self)
795 }
796 fn from_wrapping(w: Wrapping<Self>) -> Self {
797 w.0
798 }
799}
800
801impl<T> fmt::Debug for Wrapping<T>
802where
803 T: fmt::Debug,
804{
805 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
806 T::fmt(&self.0, f)
807 }
808}
809impl<T> Bounded for Wrapping<T>
810where
811 T: Bounded,
812{
813 fn maximum() -> Self {
814 Self(T::maximum())
815 }
816 fn minimum() -> Self {
817 Self(T::minimum())
818 }
819}
820impl<T> Zero for Wrapping<T>
821where
822 T: Zero,
823{
824 fn zero() -> Self {
825 Self(T::zero())
826 }
827}
828impl<T> One for Wrapping<T>
829where
830 T: One,
831{
832 fn one() -> Self {
833 Self(T::one())
834 }
835}
836impl<T> FromStr for Wrapping<T>
837where
838 T: FromStr,
839{
840 type Err = T::Err;
841 fn from_str(s: &str) -> Result<Self, Self::Err> {
842 T::from_str(s).map(Self)
843 }
844}
845impl<T> Display for Wrapping<T>
846where
847 T: Display,
848{
849 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
850 T::fmt(&self.0, f)
851 }
852}
853impl<T> IterScan for Wrapping<T>
854where
855 T: IterScan<Output = T>,
856{
857 type Output = Self;
858 fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
859 T::scan(iter).map(Self)
860 }
861}
862impl_binop!(impl<T> BitAnd bitand for Wrapping<T>);
863impl_binop!(impl<T> BitOr bitor for Wrapping<T>);
864impl_binop!(impl<T> BitXor bitxor for Wrapping<T>);
865impl_opassign!(impl<T> AddAssign add_assign for Wrapping<T> => Add add);
866impl_opassign!(impl<T> SubAssign sub_assign for Wrapping<T> => Sub sub);
867impl_opassign!(impl<T> MulAssign mul_assign for Wrapping<T> => Mul mul);
868impl_opassign!(impl<T> DivAssign div_assign for Wrapping<T> => Div div);
869impl_opassign!(impl<T> RemAssign rem_assign for Wrapping<T> => Rem rem);
870impl_opassign!(impl<T> BitAndAssign bitand_assign for Wrapping<T>);
871impl_opassign!(impl<T> BitOrAssign bitor_assign for Wrapping<T>);
872impl_opassign!(impl<T> BitXorAssign bitxor_assign for Wrapping<T>);
873impl<T> Not for Wrapping<T>
874where
875 T: Not<Output = T>,
876{
877 type Output = Self;
878 fn not(self) -> Self::Output {
879 Self(Not::not(self.0))
880 }
881}
882
883macro_rules! impl_int_base_for_wrapping {
884 ($($t:ty)*) => {
885 $(
886 impl Wrappingable for $t {}
887 impl Add for Wrapping<$t> {
888 type Output = Self;
889 fn add(self, rhs: Self) -> Self::Output {
890 Self(self.0.wrapping_add(rhs.0))
891 }
892 }
893 impl Add<$t> for Wrapping<$t> {
894 type Output = Self;
895 fn add(self, rhs: $t) -> Self::Output {
896 Self(self.0.wrapping_add(rhs))
897 }
898 }
899 impl Sub for Wrapping<$t> {
900 type Output = Self;
901 fn sub(self, rhs: Self) -> Self::Output {
902 Self(self.0.wrapping_sub(rhs.0))
903 }
904 }
905 impl Sub<$t> for Wrapping<$t> {
906 type Output = Self;
907 fn sub(self, rhs: $t) -> Self::Output {
908 Self(self.0.wrapping_sub(rhs))
909 }
910 }
911 impl Mul for Wrapping<$t> {
912 type Output = Self;
913 fn mul(self, rhs: Self) -> Self::Output {
914 Self(self.0.wrapping_mul(rhs.0))
915 }
916 }
917 impl Mul<$t> for Wrapping<$t> {
918 type Output = Self;
919 fn mul(self, rhs: $t) -> Self::Output {
920 Self(self.0.wrapping_mul(rhs))
921 }
922 }
923 impl Div for Wrapping<$t> {
924 type Output = Self;
925 fn div(self, rhs: Self) -> Self::Output {
926 Self(self.0.wrapping_div(rhs.0))
927 }
928 }
929 impl Div<$t> for Wrapping<$t> {
930 type Output = Self;
931 fn div(self, rhs: $t) -> Self::Output {
932 Self(self.0.wrapping_div(rhs))
933 }
934 }
935 impl Rem for Wrapping<$t> {
936 type Output = Self;
937 fn rem(self, rhs: Self) -> Self::Output {
938 Self(self.0.wrapping_rem(rhs.0))
939 }
940 }
941 impl Rem<$t> for Wrapping<$t> {
942 type Output = Self;
943 fn rem(self, rhs: $t) -> Self::Output {
944 Self(self.0.wrapping_rem(rhs))
945 }
946 }
947 impl Sum for Wrapping<$t> {
948 fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
949 iter.fold(Self::zero(), |acc, x| acc + x)
950 }
951 }
952 impl Product for Wrapping<$t> {
953 fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
954 iter.fold(Self::one(), |acc, x| acc * x)
955 }
956 }
957 impl IntBase for Wrapping<$t> {
958 type Error = <$t as IntBase>::Error;
959 fn div_euclid(self, rhs: Self) -> Self { Self(self.0.wrapping_div_euclid(rhs.0)) }
960 fn rem_euclid(self, rhs: Self) -> Self { Self(self.0.wrapping_rem_euclid(rhs.0)) }
961 fn pow(self, exp: u32) -> Self { Self(self.0.wrapping_pow(exp)) }
962 fn from_str_radix(src: &str, radix: u32) -> Result<Self, Self::Error> { <$t as IntBase>::from_str_radix(src, radix).map(Self) }
963 fn ilog(self, base: Self) -> u32 { self.0.ilog(base.0) }
964 fn ilog2(self) -> u32 { self.0.ilog2() }
965 fn ilog10(self) -> u32 { self.0.ilog10() }
966 fn isqrt(self) -> Self { Self(self.0.isqrt()) }
967 fn midpoint(self, rhs: Self) -> Self { Self(self.0.midpoint(rhs.0)) }
968 }
969 impl From<$t> for Wrapping<$t> {
970 fn from(t: $t) -> Self {
971 Self(t)
972 }
973 }
974 )*
975 };
976}
977impl_int_base_for_wrapping!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
978
979macro_rules! impl_unsigned_signed_for_wrapping {
980 ($($unsigned:ident $signed:ident)*) => {
981 $(
982 impl Unsigned for Wrapping<$unsigned> {
983 type Signed = Wrapping<$signed>;
984 fn signed(self) -> Self::Signed { Wrapping(self.0.signed()) }
985 fn abs_diff(self, other: Self) -> Self { Self(self.0.abs_diff(other.0)) }
986 fn div_ceil(self, rhs: Self) -> Self { Self(self.0.div_ceil(rhs.0)) }
987 fn is_power_of_two(self) -> bool { self.0.is_power_of_two() }
988 fn next_power_of_two(self) -> Self { Self(self.0.next_power_of_two()) }
989 fn is_multiple_of(self, rhs: Self) -> bool { self.0.is_multiple_of(rhs.0) }
990 fn next_multiple_of(self, rhs: Self) -> Self { Self(self.0.next_multiple_of(rhs.0)) }
991 fn gcd(self, other: Self) -> Self { Self(self.0.gcd(other.0)) }
992 fn mod_add(self, rhs: Self, modulo: Self) -> Self { Self(self.0.mod_add(rhs.0, modulo.0)) }
993 fn mod_sub(self, rhs: Self, modulo: Self) -> Self { Self(self.0.mod_sub(rhs.0, modulo.0)) }
994 fn mod_mul(self, rhs: Self, modulo: Self) -> Self { Self(self.0.mod_mul(rhs.0, modulo.0)) }
995 }
996 impl Signed for Wrapping<$signed> {
997 type Unsigned = Wrapping<$unsigned>;
998 fn unsigned(self) -> Self::Unsigned { Wrapping(self.0.unsigned()) }
999 fn abs(self) -> Self { Self(self.0.wrapping_abs()) }
1000 fn abs_diff(self, other: Self) -> Self::Unsigned { Wrapping(self.0.abs_diff(other.0)) }
1001 fn is_negative(self) -> bool { self.0.is_negative() }
1002 fn is_positive(self) -> bool { self.0.is_positive() }
1003 fn signum(self) -> Self { Self(self.0.signum()) }
1004 }
1005 impl Neg for Wrapping<$signed> {
1006 type Output = Self;
1007 fn neg(self) -> Self::Output {
1008 Self(self.0.wrapping_neg())
1009 }
1010 }
1011 )*
1012 };
1013}
1014impl_unsigned_signed_for_wrapping!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
1015
1016macro_rules! impl_binary_repr_for_wrapping {
1017 ($($t:ty)*) => {
1018 $(
1019 impl Shl<u32> for Wrapping<$t> {
1020 type Output = Self;
1021 fn shl(self, rhs: u32) -> Self::Output {
1022 Self(self.0.wrapping_shl(rhs))
1023 }
1024 }
1025 impl Shr<u32> for Wrapping<$t> {
1026 type Output = Self;
1027 fn shr(self, rhs: u32) -> Self::Output {
1028 Self(self.0.wrapping_shr(rhs))
1029 }
1030 }
1031 impl ShlAssign<u32> for Wrapping<$t> {
1032 fn shl_assign(&mut self, rhs: u32) {
1033 *self = Shl::shl(*self, rhs);
1034 }
1035 }
1036 impl ShrAssign<u32> for Wrapping<$t> {
1037 fn shr_assign(&mut self, rhs: u32) {
1038 *self = Shr::shr(*self, rhs);
1039 }
1040 }
1041 impl BinaryRepr for Wrapping<$t> {
1042 fn count_ones(self) -> u32 { self.0.count_ones() }
1043 fn count_zeros(self) -> u32 { self.0.count_zeros() }
1044 fn leading_ones(self) -> u32 { self.0.leading_ones() }
1045 fn leading_zeros(self) -> u32 { self.0.leading_zeros() }
1046 fn reverse_bits(self) -> Self { Self(self.0.reverse_bits()) }
1047 fn rotate_left(self, n: u32) -> Self { Self(self.0.rotate_left(n)) }
1048 fn rotate_right(self, n: u32) -> Self { Self(self.0.rotate_right(n)) }
1049 fn swap_bytes(self) -> Self { Self(self.0.swap_bytes()) }
1050 fn trailing_ones(self) -> u32 { self.0.trailing_ones() }
1051 fn trailing_zeros(self) -> u32 { self.0.trailing_zeros() }
1052 }
1053 )*
1054 };
1055}
1056impl_binary_repr_for_wrapping!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
1057
1058#[cfg(test)]
1059mod tests {
1060 use super::*;
1061 use crate::tools::Xorshift;
1062 const Q: usize = 10_000;
1063
1064 mod int_base {
1065 macro_rules! test_intbase {
1066 ($($t:ident)*) => {
1067 $(
1068 mod $t {
1069 use super::super::*;
1070
1071 #[test]
1072 fn test_intbase() {
1073 assert_eq!(<$t as IntBase>::div_euclid(10, 3), 3);
1074 assert_eq!(<$t as IntBase>::rem_euclid(10, 3), 1);
1075 assert_eq!(<$t as IntBase>::pow(10, 2), 100);
1076 assert_eq!(<$t as IntBase>::from_str_radix("1a", 16).unwrap(), 26 as $t);
1077 assert_eq!(<$t as IntBase>::ilog(100 as $t, 10 as $t), 2);
1078 assert_eq!(<$t as IntBase>::ilog2(16 as $t), 4);
1079 assert_eq!(<$t as IntBase>::ilog10(100 as $t), 2);
1080 assert_eq!(<$t as IntBase>::isqrt(16 as $t), 4 as $t);
1081 assert_eq!(<$t as IntBase>::midpoint(10 as $t, 20 as $t), 15 as $t);
1082 }
1083 }
1084 )*
1085 };
1086 }
1087 test_intbase!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
1088 }
1089
1090 mod unsigned {
1091 use super::*;
1092
1093 macro_rules! test_unsigned {
1094 ($($t:ident)*) => {
1095 $(
1096 mod $t {
1097 use super::super::*;
1098 const A: $t = $t::MAX / 2;
1099 fn gcd(mut a: $t, mut b: $t) -> $t {
1100 while b != 0 {
1101 a %= b;
1102 std::mem::swap(&mut a, &mut b);
1103 }
1104 a
1105 }
1106 #[test]
1107 fn test_gcd() {
1108 let mut rng = Xorshift::default();
1109 for (a, b) in rng.random_iter((0..=A, 0..=A)).take(Q) {
1110 assert_eq!(a.gcd(b), gcd(a, b));
1111 }
1112 assert_eq!($t::zero().gcd(0), 0);
1113 assert_eq!($t::zero().gcd(100), 100);
1114 }
1115 #[test]
1116 fn test_mod_inv() {
1117 let mut rng = Xorshift::default();
1118 for _ in 0..Q {
1119 let m = rng.random(2..=A);
1120 let a = rng.random(1..m);
1121 let g = a.gcd(m);
1122 let m = m / g;
1123 let a = a / g;
1124 let x = a.mod_inv(m);
1125 assert!(x < m);
1126 assert_eq!(a as u128 * x as u128 % m as u128, 1);
1127 }
1128 }
1129 #[test]
1130 fn test_mod_operate() {
1131 let mut rng = Xorshift::default();
1132 for _ in 0..Q {
1133 for ub in [10, A] {
1134 let m = rng.random(2..=ub);
1135 let a = rng.random(0..m);
1136 let b = rng.random(0..m);
1137 assert_eq!(a.mod_add(b, m), ((a as u128 + b as u128) % m as u128) as $t);
1138 assert_eq!(a.mod_sub(b, m), ((a as u128 + m as u128 - b as u128) % m as u128) as $t);
1139 assert_eq!(a.mod_mul(b, m), (a as u128 * b as u128 % m as u128) as $t);
1140 assert_eq!(a.mod_mul(b, m), (a as u128).mod_mul(b as u128, m as u128) as $t);
1141 assert_eq!(a.mod_neg(m), ((m as u128 - a as u128) % m as u128) as $t);
1142 }
1143 }
1144 }
1145 #[test]
1146 fn test_unsigned() {
1147 assert_eq!(<$t as Unsigned>::signed(0), 0);
1148 assert_eq!(<$t as Unsigned>::abs_diff(10, 20), 10);
1149 assert_eq!(<$t as Unsigned>::div_ceil(10, 3), 4);
1150 assert_eq!(<$t as Unsigned>::is_power_of_two(16), true);
1151 assert_eq!(<$t as Unsigned>::is_power_of_two(10), false);
1152 assert_eq!(<$t as Unsigned>::next_power_of_two(10), 16);
1153 assert_eq!(<$t as Unsigned>::is_multiple_of(20, 5), true);
1154 assert_eq!(<$t as Unsigned>::is_multiple_of(20, 6), false);
1155 assert_eq!(<$t as Unsigned>::next_multiple_of(20, 6), 24);
1156 assert_eq!(<$t as Unsigned>::gcd(100, 80), 20);
1157 assert_eq!(<$t as Unsigned>::lcm(12, 15), 60);
1158 assert_eq!(<$t as Unsigned>::lcm(0, 1), 0);
1159 assert_eq!(<$t as Unsigned>::lcm(0, 0), 0);
1160 }
1161 }
1162 )*
1163 };
1164 }
1165 test_unsigned!(u8 u16 u32 u64 usize);
1166
1167 #[test]
1168 fn test_mod_mul_u128() {
1169 fn naive_mod_mul(a: u128, b: u128, m: u128) -> u128 {
1170 assert!(m != 0);
1171 let a = [a as u64, (a >> 64) as u64];
1172 let b = [b as u64, (b >> 64) as u64];
1173 let mut res = 0u128;
1174 for (i, &a) in a.iter().enumerate() {
1175 for (j, &b) in b.iter().enumerate() {
1176 let mut x = (a as u128) * (b as u128) % m;
1177 for _ in 0..(i + j) * 64 {
1178 x = x.mod_add(x, m);
1179 }
1180 res = res.mod_add(x, m);
1181 }
1182 }
1183 res
1184 }
1185
1186 let mut rng = Xorshift::default();
1187 for _ in 0..100 {
1188 for a in [1, 10, u32::MAX as _, u64::MAX as _, u128::MAX] {
1189 for b in [1, 10, u32::MAX as _, u64::MAX as _, u128::MAX] {
1190 for c in [1, 10, u32::MAX as _, u64::MAX as _, u128::MAX] {
1191 let m = rng.random(1..=c);
1192 let x = rng.random(0..a.min(m));
1193 let y = rng.random(0..b.min(m));
1194 assert_eq!(x.mod_mul(y, m), naive_mod_mul(x, y, m));
1195 let x = rng.random(0..a);
1196 let y = rng.random(0..b);
1197 assert_eq!(x.mod_mul(y, m), naive_mod_mul(x, y, m));
1198 }
1199 }
1200 }
1201 }
1202 }
1203
1204 #[test]
1205 fn test_rem() {
1206 fn naive_rem(u: [u64; 4], v: u128) -> u128 {
1207 assert!(v != 0);
1208 let mut u = [
1209 ((u[1] as u128) << 64) | (u[0] as u128),
1210 ((u[3] as u128) << 64) | (u[2] as u128),
1211 ];
1212 let mut v_mul_2 = vec![[v, 0]];
1213 while v_mul_2.last().unwrap()[1].leading_zeros() != 0 {
1214 let [v_lo, v_hi] = *v_mul_2.last().unwrap();
1215 v_mul_2.push([v_lo << 1, v_hi << 1 | (v_lo >> 127)]);
1216 }
1217 v_mul_2.reverse();
1218 for [v_lo, v_hi] in v_mul_2 {
1219 let [u_lo, u_hi] = u;
1220 if (u_hi > v_hi) || (u_hi == v_hi && u_lo >= v_lo) {
1221 let (new_lo, carry) = u_lo.overflowing_sub(v_lo);
1222 let new_hi = u_hi - v_hi - (carry as u128);
1223 u = [new_lo, new_hi];
1224 }
1225 }
1226 u[0]
1227 }
1228 let mut rng = Xorshift::default();
1229 for _ in 0..1000 {
1230 let mut u = [0u64; 4];
1231 for k in 0..4 {
1232 for a in [1, 10, u32::MAX as _, u64::MAX] {
1233 u[k] = rng.random(..a);
1234 for b in [1, 10, u128::MAX] {
1235 let v = rng.random(1..=b);
1236 assert_eq!(rem_u256_by_u128(u, v), naive_rem(u, v));
1237 }
1238 }
1239 }
1240 }
1241 let u = [0, 0, 0, 1 << 63];
1242 let v = (1 << 127) + 1;
1243 assert_eq!(rem_u256_by_u128(u, v), naive_rem(u, v));
1244 }
1245 }
1246
1247 mod signed {
1248 macro_rules! test_signed {
1249 ($($t:ident)*) => {
1250 $(
1251 mod $t {
1252 use super::super::*;
1253 const A: $t = $t::MAX / 2;
1254 #[test]
1255 fn test_extgcd() {
1256 let mut rng = Xorshift::default();
1257 for (a, b) in rng.random_iter((-A..=A, -A..=A)).take(Q) {
1258 let ExtendedGcd { g, x, y } = a.extgcd(b);
1259 assert_eq!(g, a.abs().unsigned().gcd(b.abs().unsigned()));
1260 assert_eq!(a as i128 * x as i128 + b as i128 * y as i128, g.signed() as i128);
1261 }
1262 }
1263 #[test]
1264 fn test_signed() {
1265 assert_eq!(<$t as Signed>::unsigned(0), 0);
1266 assert_eq!(<$t as Signed>::abs(-10), 10);
1267 assert_eq!(<$t as Signed>::abs_diff(10, -20), 30);
1268 assert!(!<$t as Signed>::is_negative(10));
1269 assert!(<$t as Signed>::is_negative(-10));
1270 assert!(<$t as Signed>::is_positive(10));
1271 assert!(!<$t as Signed>::is_positive(-10));
1272 assert_eq!(<$t as Signed>::signum(10), 1);
1273 assert_eq!(<$t as Signed>::signum(-10), -1);
1274 assert_eq!(<$t as Signed>::signum(0), 0);
1275 }
1276 }
1277 )*
1278 };
1279 }
1280 test_signed!(i8 i16 i32 i64 isize);
1281 }
1282
1283 macro_rules! test_binary_repr {
1284 ($($t:ident)*) => {
1285 $(
1286 mod $t {
1287 use super::super::*;
1288 #[test]
1289 fn test_binary_repr() {
1290 assert_eq!(<$t as BinaryRepr>::count_ones(0b1010), 2);
1291 assert_eq!(<$t as BinaryRepr>::count_zeros(0b1010), <$t>::BITS - 2);
1292 assert_eq!(<$t as BinaryRepr>::leading_ones(!0b0010), <$t>::BITS - 2);
1293 assert_eq!(<$t as BinaryRepr>::leading_zeros(0b0010), <$t>::BITS - 2);
1294 assert_eq!(<$t as BinaryRepr>::reverse_bits(0b101), 0b101 << (<$t>::BITS - 3));
1295 assert_eq!(<$t as BinaryRepr>::rotate_left(0b0001_0010, 2), 0b0100_1000);
1296 assert_eq!(<$t as BinaryRepr>::rotate_right(0b0001_0010, <$t>::BITS - 2), 0b0100_1000);
1297 assert_eq!(<$t as BinaryRepr>::swap_bytes(0b0001_0010), 0b0001_0010 << (<$t>::BITS - 8));
1298 assert_eq!(<$t as BinaryRepr>::trailing_ones(!0b0100), 2);
1299 assert_eq!(<$t as BinaryRepr>::trailing_zeros(0b0100), 2);
1300 }
1301 }
1302 )*
1303 }
1304 }
1305 mod binary_repr {
1306 test_binary_repr!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
1307 }
1308
1309 mod saturating {
1310 macro_rules! test_saturating {
1311 ($($unsigned:ident $signed:ident)*) => {
1312 $(
1313 mod $unsigned {
1314 use super::super::*;
1315 type S = Saturating<$unsigned>;
1316
1317 test_saturating!(@common $unsigned);
1318 test_saturating!(@unsigned $unsigned);
1319 }
1320 mod $signed {
1321 use super::super::*;
1322 type S = Saturating<$signed>;
1323
1324 test_saturating!(@common $signed);
1325 test_saturating!(@signed $signed);
1326 }
1327 )*
1328 };
1329 (@common $t:ident) => {
1330 macro_rules! assign {
1331 ($op:tt, $left:expr, $right:expr) => {{
1332 let mut a = $left;
1333 a $op $right;
1334 a
1335 }};
1336 }
1337
1338 #[test]
1339 fn test_saturating() {
1340 assert_eq!((1 as $t).to_saturating(), S::from(1));
1341 assert_eq!($t::from_saturating((1 as $t).to_saturating()), 1 as $t);
1342 assert_eq!(S::maximum(), S::from($t::MAX));
1343 assert_eq!(S::minimum(), S::from($t::MIN));
1344 assert_eq!(S::zero(), S::from(0));
1345 assert_eq!(S::one(), S::from(1));
1346 assert_eq!(S::from(1 as $t).to_string(), "1");
1347 assert_eq!(S::from_str("123").unwrap(), S::from(123));
1348 assert_eq!(format!("{:?}", S::from(123)), "123");
1349 assert_eq!(S::scan(&mut ["123"].iter().map(|s| *s)).unwrap(), S::from(123));
1350 assert_eq!(S::from(1) + S::from(2), S::from(3));
1351 assert_eq!(S::from(1) + 2, S::from(3));
1352 assert_eq!(S::from(3) - S::from(1), S::from(2));
1353 assert_eq!(S::from(3) - 1, S::from(2));
1354 assert_eq!(S::from(2) * S::from(3), S::from(6));
1355 assert_eq!(S::from(2) * 3, S::from(6));
1356 assert_eq!(S::from(6) / S::from(3), S::from(2));
1357 assert_eq!(S::from(6) / 3, S::from(2));
1358 assert_eq!(S::from(7) % S::from(4), S::from(3));
1359 assert_eq!(S::from(7) % 4, S::from(3));
1360 assert_eq!(S::from(1) & S::from(3), S::from(1));
1361 assert_eq!(S::from(1) & 3, S::from(1));
1362 assert_eq!(S::from(1) | S::from(2), S::from(3));
1363 assert_eq!(S::from(1) | 2, S::from(3));
1364 assert_eq!(S::from(3) ^ S::from(1), S::from(2));
1365 assert_eq!(S::from(3) ^ 1, S::from(2));
1366 assert_eq!(S::from(1) << 2, S::from(4));
1367 assert_eq!(S::from(4) >> 2, S::from(1));
1368 assert_eq!(assign!(+=, S::from(1), S::from(2)), S::from(3));
1369 assert_eq!(assign!(+=, S::from(1), 2), S::from(3));
1370 assert_eq!(assign!(-=, S::from(3), S::from(1)), S::from(2));
1371 assert_eq!(assign!(-=, S::from(3), 1), S::from(2));
1372 assert_eq!(assign!(*=, S::from(2), S::from(3)), S::from(6));
1373 assert_eq!(assign!(*=, S::from(2), 3), S::from(6));
1374 assert_eq!(assign!(/=, S::from(6), S::from(3)), S::from(2));
1375 assert_eq!(assign!(/=, S::from(6), 3), S::from(2));
1376 assert_eq!(assign!(%=, S::from(7), S::from(4)), S::from(3));
1377 assert_eq!(assign!(%=, S::from(7), 4), S::from(3));
1378 assert_eq!(assign!(&=, S::from(1), S::from(3)), S::from(1));
1379 assert_eq!(assign!(&=, S::from(1), 3), S::from(1));
1380 assert_eq!(assign!(|=, S::from(1), S::from(2)), S::from(3));
1381 assert_eq!(assign!(|=, S::from(1), 2), S::from(3));
1382 assert_eq!(assign!(^=, S::from(3), S::from(1)), S::from(2));
1383 assert_eq!(assign!(^=, S::from(3), 1), S::from(2));
1384 assert_eq!(assign!(<<=, S::from(1), 2), S::from(4));
1385 assert_eq!(assign!(>>=, S::from(4), 2), S::from(1));
1386 assert_eq!(!S::from(1), S::from(!(1 as $t)));
1387 assert_eq!([S::from(1), S::from(2)].into_iter().sum::<S>(), S::from(3));
1388 assert_eq!([S::from(2), S::from(3)].into_iter().product::<S>(), S::from(6));
1389 assert_eq!(S::from(10).div_euclid(S::from(3)), S::from(3));
1390 assert_eq!(S::from(10).rem_euclid(S::from(3)), S::from(1));
1391 assert_eq!(S::from(10).pow(2), S::from(100));
1392 assert_eq!(S::from_str_radix("1a", 16).unwrap(), S::from(26));
1393 assert_eq!(S::from(100).ilog(S::from(10)), 2);
1394 assert_eq!(S::from(16).ilog2(), 4);
1395 assert_eq!(S::from(100).ilog10(), 2);
1396 assert_eq!(S::from(0b1010).count_ones(), 2);
1397 assert_eq!(S::from(0b1010).count_zeros(), <$t>::BITS - 2);
1398 assert_eq!(S::from(!0b0010).leading_ones(), <$t>::BITS - 2);
1399 assert_eq!(S::from(0b0010).leading_zeros(), <$t>::BITS - 2);
1400 assert_eq!(S::from(0b101).reverse_bits(), S::from(0b101 << (<$t>::BITS - 3)));
1401 assert_eq!(S::from(0b0001_0010).rotate_left(2), S::from(0b0100_1000));
1402 assert_eq!(S::from(0b0001_0010).rotate_right(<$t>::BITS - 2), S::from(0b0100_1000));
1403 assert_eq!(S::from(0b0001_0010).swap_bytes(), S::from(0b0001_0010 << (<$t>::BITS - 8)));
1404 assert_eq!(S::from(!0b0100).trailing_ones(), 2);
1405 assert_eq!(S::from(0b0100).trailing_zeros(), 2);
1406 }
1407 };
1408 (@unsigned $t:ident) => {
1409 #[test]
1410 fn test_saturating_unsigned() {
1411 assert_eq!(S::from(0).signed(), Saturating::from(0));
1412 assert_eq!(S::from(10).abs_diff(S::from(20)), S::from(10));
1413 assert_eq!(S::from(10).next_power_of_two(), S::from(16));
1414 assert_eq!(S::from(100).gcd(S::from(80)), S::from(20));
1415 assert_eq!(S::from(100).mod_add(S::from(80), S::from(150)), S::from(30));
1416 assert_eq!(S::from(100).mod_sub(S::from(80), S::from(150)), S::from(20));
1417 assert_eq!(S::from(100).mod_mul(S::from(80), S::from(150)), S::from(50));
1418 }
1419 };
1420 (@signed $t:ident) => {
1421 #[test]
1422 fn test_saturating_signed() {
1423 assert_eq!(S::from(0).unsigned(), Saturating::from(0));
1424 assert_eq!(S::from(-10).abs(), S::from(10));
1425 assert_eq!(S::from(10).abs_diff(S::from(-20)), Saturating::from(30));
1426 assert!(!S::from(10).is_negative());
1427 assert!(S::from(-10).is_negative());
1428 assert!(S::from(10).is_positive());
1429 assert!(!S::from(-10).is_positive());
1430 assert_eq!(S::from(10).signum(), S::from(1));
1431 assert_eq!(S::from(-10).signum(), S::from(-1));
1432 assert_eq!(S::from(0).signum(), S::from(0));
1433 assert_eq!(-S::from(1), S::from(-1));
1434 }
1435 };
1436 }
1437 test_saturating!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
1438 }
1439
1440 mod wrapping {
1441 macro_rules! test_wrapping {
1442 ($($unsigned:ident $signed:ident)*) => {
1443 $(
1444 mod $unsigned {
1445 use super::super::*;
1446 type W = Wrapping<$unsigned>;
1447
1448 test_wrapping!(@common $unsigned);
1449 test_wrapping!(@unsigned $unsigned);
1450 }
1451 mod $signed {
1452 use super::super::*;
1453 type W = Wrapping<$signed>;
1454
1455 test_wrapping!(@common $signed);
1456 test_wrapping!(@signed $signed);
1457 }
1458 )*
1459 };
1460 (@common $t:ident) => {
1461 macro_rules! assign {
1462 ($op:tt, $left:expr, $right:expr) => {{
1463 let mut a = $left;
1464 a $op $right;
1465 a
1466 }};
1467 }
1468
1469 #[test]
1470 fn test_wrapping() {
1471 assert_eq!((1 as $t).to_wrapping(), W::from(1));
1472 assert_eq!($t::from_wrapping((1 as $t).to_wrapping()), 1 as $t);
1473 assert_eq!(W::maximum(), W::from($t::MAX));
1474 assert_eq!(W::minimum(), W::from($t::MIN));
1475 assert_eq!(W::zero(), W::from(0));
1476 assert_eq!(W::one(), W::from(1));
1477 assert_eq!(W::from(1 as $t).to_string(), "1");
1478 assert_eq!(W::from_str("123").unwrap(), W::from(123));
1479 assert_eq!(format!("{:?}", W::from(123)), "123");
1480 assert_eq!(W::scan(&mut ["123"].iter().map(|s| *s)).unwrap(), W::from(123));
1481 assert_eq!(W::from(1) + W::from(2), W::from(3));
1482 assert_eq!(W::from(1) + 2, W::from(3));
1483 assert_eq!(W::from(3) - W::from(1), W::from(2));
1484 assert_eq!(W::from(3) - 1, W::from(2));
1485 assert_eq!(W::from(2) * W::from(3), W::from(6));
1486 assert_eq!(W::from(2) * 3, W::from(6));
1487 assert_eq!(W::from(6) / W::from(3), W::from(2));
1488 assert_eq!(W::from(6) / 3, W::from(2));
1489 assert_eq!(W::from(7) % W::from(4), W::from(3));
1490 assert_eq!(W::from(7) % 4, W::from(3));
1491 assert_eq!(W::from(1) & W::from(3), W::from(1));
1492 assert_eq!(W::from(1) & 3, W::from(1));
1493 assert_eq!(W::from(1) | W::from(2), W::from(3));
1494 assert_eq!(W::from(1) | 2, W::from(3));
1495 assert_eq!(W::from(3) ^ W::from(1), W::from(2));
1496 assert_eq!(W::from(3) ^ 1, W::from(2));
1497 assert_eq!(W::from(1) << 2, W::from(4));
1498 assert_eq!(W::from(4) >> 2, W::from(1));
1499 assert_eq!(assign!(+=, W::from(1), W::from(2)), W::from(3));
1500 assert_eq!(assign!(+=, W::from(1), 2), W::from(3));
1501 assert_eq!(assign!(-=, W::from(3), W::from(1)), W::from(2));
1502 assert_eq!(assign!(-=, W::from(3), 1), W::from(2));
1503 assert_eq!(assign!(*=, W::from(2), W::from(3)), W::from(6));
1504 assert_eq!(assign!(*=, W::from(2), 3), W::from(6));
1505 assert_eq!(assign!(/=, W::from(6), W::from(3)), W::from(2));
1506 assert_eq!(assign!(/=, W::from(6), 3), W::from(2));
1507 assert_eq!(assign!(%=, W::from(7), W::from(4)), W::from(3));
1508 assert_eq!(assign!(%=, W::from(7), 4), W::from(3));
1509 assert_eq!(assign!(&=, W::from(1), W::from(3)), W::from(1));
1510 assert_eq!(assign!(&=, W::from(1), 3), W::from(1));
1511 assert_eq!(assign!(|=, W::from(1), W::from(2)), W::from(3));
1512 assert_eq!(assign!(|=, W::from(1), 2), W::from(3));
1513 assert_eq!(assign!(^=, W::from(3), W::from(1)), W::from(2));
1514 assert_eq!(assign!(^=, W::from(3), 1), W::from(2));
1515 assert_eq!(assign!(<<=, W::from(1), 2), W::from(4));
1516 assert_eq!(assign!(>>=, W::from(4), 2), W::from(1));
1517 assert_eq!(!W::from(1), W::from(!(1 as $t)));
1518 assert_eq!([W::from(1), W::from(2)].into_iter().sum::<W>(), W::from(3));
1519 assert_eq!([W::from(2), W::from(3)].into_iter().product::<W>(), W::from(6));
1520 assert_eq!(W::from(10).div_euclid(W::from(3)), W::from(3));
1521 assert_eq!(W::from(10).rem_euclid(W::from(3)), W::from(1));
1522 assert_eq!(W::from(10).pow(2), W::from(100));
1523 assert_eq!(W::from_str_radix("1a", 16).unwrap(), W::from(26));
1524 assert_eq!(W::from(100).ilog(W::from(10)), 2);
1525 assert_eq!(W::from(16).ilog2(), 4);
1526 assert_eq!(W::from(100).ilog10(), 2);
1527 assert_eq!(W::from(0b1010).count_ones(), 2);
1528 assert_eq!(W::from(0b1010).count_zeros(), <$t>::BITS - 2);
1529 assert_eq!(W::from(!0b0010).leading_ones(), <$t>::BITS - 2);
1530 assert_eq!(W::from(0b0010).leading_zeros(), <$t>::BITS - 2);
1531 assert_eq!(W::from(0b101).reverse_bits(), W::from(0b101 << (<$t>::BITS - 3)));
1532 assert_eq!(W::from(0b0001_0010).rotate_left(2), W::from(0b0100_1000));
1533 assert_eq!(W::from(0b0001_0010).rotate_right(<$t>::BITS - 2), W::from(0b0100_1000));
1534 assert_eq!(W::from(0b0001_0010).swap_bytes(), W::from(0b0001_0010 << (<$t>::BITS - 8)));
1535 assert_eq!(W::from(!0b0100).trailing_ones(), 2);
1536 assert_eq!(W::from(0b0100).trailing_zeros(), 2);
1537 }
1538 };
1539 (@unsigned $t:ident) => {
1540 #[test]
1541 fn test_wrapping_unsigned() {
1542 assert_eq!(W::from(0).signed(), Wrapping::from(0));
1543 assert_eq!(W::from(10).abs_diff(W::from(20)), W::from(10));
1544 assert_eq!(W::from(10).next_power_of_two(), W::from(16));
1545 assert_eq!(W::from(100).gcd(W::from(80)), W::from(20));
1546 assert_eq!(W::from(100).mod_add(W::from(80), W::from(150)), W::from(30));
1547 assert_eq!(W::from(100).mod_sub(W::from(80), W::from(150)), W::from(20));
1548 assert_eq!(W::from(100).mod_mul(W::from(80), W::from(150)), W::from(50));
1549 }
1550 };
1551 (@signed $t:ident) => {
1552 #[test]
1553 fn test_wrapping_signed() {
1554 assert_eq!(W::from(0).unsigned(), Wrapping::from(0));
1555 assert_eq!(W::from(-10).abs(), W::from(10));
1556 assert_eq!(W::from(10).abs_diff(W::from(-20)), Wrapping::from(30));
1557 assert!(!W::from(10).is_negative());
1558 assert!(W::from(-10).is_negative());
1559 assert!(W::from(10).is_positive());
1560 assert!(!W::from(-10).is_positive());
1561 assert_eq!(W::from(10).signum(), W::from(1));
1562 assert_eq!(W::from(-10).signum(), W::from(-1));
1563 assert_eq!(W::from(0).signum(), W::from(0));
1564 assert_eq!(-W::from(1), W::from(-1));
1565 }
1566 };
1567 }
1568 test_wrapping!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
1569 }
1570}