1use std::fmt::Debug;
4use std::iter::{Product, Sum};
5use std::ops::{
6 Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div, DivAssign,
7 Mul, MulAssign, Neg, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub, SubAssign,
8};
9
10pub trait Number:
12 Copy
13 + Debug
14 + Default
15 + PartialEq
16 + PartialOrd
17 + Add<Output = Self>
18 + AddAssign
19 + Div<Output = Self>
20 + DivAssign
21 + Mul<Output = Self>
22 + MulAssign
23 + Rem<Output = Self>
24 + RemAssign
25 + Sub<Output = Self>
26 + SubAssign
27 + Sum<Self>
28 + for<'a> Sum<&'a Self>
29 + Product<Self>
30 + for<'a> Product<&'a Self>
31{
32 const ZERO: Self;
33 const ONE: Self;
34 const MIN: Self;
35 const MAX: Self;
36
37 #[must_use]
38 fn abs(self) -> Self;
39 #[must_use]
40 fn rem_euclid(self, rhs: Self) -> Self;
41 #[must_use]
42 fn squared_diff(self, rhs: Self) -> Self;
43}
44
45pub trait Signed: Number + Neg<Output = Self> + From<i8> {
47 const MINUS_ONE: Self;
48}
49
50pub trait Integer:
52 Number
53 + Not<Output = Self>
54 + BitAnd<Output = Self>
55 + BitAndAssign
56 + BitOr<Output = Self>
57 + BitOrAssign
58 + BitXor<Output = Self>
59 + BitXorAssign
60 + Shl<Output = Self>
61 + Shl<u32, Output = Self>
62 + ShlAssign
63 + ShlAssign<u32>
64 + Shr<Output = Self>
65 + Shr<u32, Output = Self>
66 + ShrAssign
67 + ShrAssign<u32>
68 + TryInto<i128>
69 + From<bool>
70{
71 type NonZero: Copy + TryFrom<Self> + Into<Self>;
72 type Unsigned: UnsignedInteger<Signed = Self::Signed>;
73 type Signed: SignedInteger<Unsigned = Self::Unsigned>;
74
75 const BITS: u32;
76
77 #[must_use]
78 fn abs_diff(self, rhs: Self) -> Self::Unsigned;
79 #[must_use]
80 fn checked_add(self, rhs: Self) -> Option<Self>;
81 #[must_use]
82 fn checked_sub(self, rhs: Self) -> Option<Self>;
83 #[must_use]
84 fn checked_mul(self, rhs: Self) -> Option<Self>;
85 #[must_use]
86 fn isolate_lowest_one(self) -> Self;
87 #[must_use]
88 fn lowest_one(self) -> Option<u32>;
89 #[must_use]
90 fn trailing_ones(self) -> u32;
91 #[must_use]
92 fn trailing_zeros(self) -> u32;
93 #[must_use]
94 fn unsigned_abs(self) -> Self::Unsigned;
95 #[must_use]
96 fn saturating_sub_0(self, rhs: Self) -> Self::Unsigned;
97}
98
99pub trait UnsignedInteger:
101 Integer<Unsigned = Self> + From<u8> + TryFrom<u128, Error: Debug>
102{
103 const SAFE_DIGITS: usize;
105
106 #[must_use]
107 fn cast_signed(self) -> Self::Signed;
108
109 #[must_use]
110 fn wrapping_add_signed(self, rhs: Self::Signed) -> Self;
111
112 #[must_use]
113 fn wrapping_sub(self, rhs: Self) -> Self;
114}
115
116pub trait SignedInteger: Integer<Signed = Self> + Signed {
118 #[must_use]
119 fn cast_unsigned(self) -> Self::Unsigned;
120}
121
122macro_rules! number_impl {
123 (int => $($u:ident: $s:ident ),+) => {
124 $(impl Number for $u {
125 const ZERO: Self = 0;
126 const ONE: Self = 1;
127 const MIN: Self = Self::MIN;
128 const MAX: Self = Self::MAX;
129
130 #[inline]
131 fn abs(self) -> Self {
132 self }
134
135 #[inline]
136 fn rem_euclid(self, rhs: Self) -> Self {
137 self.rem_euclid(rhs)
138 }
139
140 #[inline]
141 fn squared_diff(self, rhs: Self) -> Self {
142 let diff = self.abs_diff(rhs);
143 diff * diff
144 }
145 })+
146
147 $(impl Integer for $u {
148 type NonZero = std::num::NonZero<$u>;
149 type Unsigned = $u;
150 type Signed = $s;
151
152 const BITS: u32 = $u::BITS;
153
154 #[inline]
155 fn abs_diff(self, rhs: Self) -> Self::Unsigned {
156 self.abs_diff(rhs)
157 }
158 #[inline]
159 fn checked_add(self, rhs: Self) -> Option<Self> {
160 self.checked_add(rhs)
161 }
162 #[inline]
163 fn checked_sub(self, rhs: Self) -> Option<Self> {
164 self.checked_sub(rhs)
165 }
166 #[inline]
167 fn checked_mul(self, rhs: Self) -> Option<Self> {
168 self.checked_mul(rhs)
169 }
170 #[inline]
171 fn isolate_lowest_one(self) -> Self {
172 self.isolate_lowest_one()
173 }
174 #[inline]
175 fn lowest_one(self) -> Option<u32> {
176 self.lowest_one()
177 }
178 #[inline]
179 fn trailing_ones(self) -> u32 {
180 self.trailing_ones()
181 }
182 #[inline]
183 fn trailing_zeros(self) -> u32 {
184 self.trailing_zeros()
185 }
186 #[inline]
187 fn unsigned_abs(self) -> Self::Unsigned {
188 self }
190 #[inline]
191 fn saturating_sub_0(self, rhs: Self) -> Self::Unsigned {
192 self.saturating_sub(rhs)
193 }
194 })+
195
196 $(impl UnsignedInteger for $u {
197 const SAFE_DIGITS: usize = $u::MAX.ilog10() as usize;
198
199 #[inline]
200 fn cast_signed(self) -> Self::Signed {
201 self.cast_signed()
202 }
203
204 #[inline]
205 fn wrapping_add_signed(self, rhs: Self::Signed) -> Self {
206 self.wrapping_add_signed(rhs)
207 }
208
209 #[inline]
210 fn wrapping_sub(self, rhs: Self) -> Self {
211 self.wrapping_sub(rhs)
212 }
213 })+
214
215 $(impl Number for $s {
216 const ZERO: Self = 0;
217 const ONE: Self = 1;
218 const MIN: Self = Self::MIN;
219 const MAX: Self = Self::MAX;
220
221 #[inline]
222 fn abs(self) -> Self {
223 self.abs()
224 }
225
226 #[inline]
227 fn rem_euclid(self, rhs: Self) -> Self {
228 self.rem_euclid(rhs)
229 }
230
231 #[inline]
232 fn squared_diff(self, rhs: Self) -> Self {
233 let diff = self - rhs;
234 diff * diff
235 }
236 })+
237
238 $(impl Signed for $s {
239 const MINUS_ONE: Self = -Self::ONE;
240 })+
241
242 $(impl Integer for $s {
243 type NonZero = std::num::NonZero<$s>;
244 type Unsigned = $u;
245 type Signed = $s;
246
247 const BITS: u32 = $s::BITS;
248
249 #[inline]
250 fn abs_diff(self, rhs: Self) -> Self::Unsigned {
251 self.abs_diff(rhs)
252 }
253 #[inline]
254 fn checked_add(self, rhs: Self) -> Option<Self> {
255 self.checked_add(rhs)
256 }
257 #[inline]
258 fn checked_sub(self, rhs: Self) -> Option<Self> {
259 self.checked_sub(rhs)
260 }
261 #[inline]
262 fn checked_mul(self, rhs: Self) -> Option<Self> {
263 self.checked_mul(rhs)
264 }
265 #[inline]
266 fn isolate_lowest_one(self) -> Self {
267 self.isolate_lowest_one()
268 }
269 #[inline]
270 fn lowest_one(self) -> Option<u32> {
271 self.lowest_one()
272 }
273 #[inline]
274 fn trailing_ones(self) -> u32 {
275 self.trailing_ones()
276 }
277 #[inline]
278 fn trailing_zeros(self) -> u32 {
279 self.trailing_zeros()
280 }
281 #[inline]
282 fn unsigned_abs(self) -> Self::Unsigned {
283 self.unsigned_abs()
284 }
285 #[inline]
286 #[expect(clippy::cast_sign_loss)]
287 fn saturating_sub_0(self, rhs: Self) -> Self::Unsigned {
288 let diff = (self as $u).wrapping_sub(rhs as $u);
291 let mask = (0 as $u).wrapping_sub($u::from(self >= rhs));
292 diff & mask
293 }
294 })+
295
296 $(impl SignedInteger for $s {
297 #[inline]
298 fn cast_unsigned(self) -> Self::Unsigned {
299 self.cast_unsigned()
300 }
301 })+
302 };
303 (float => $($t:ident),+) => {$(
304 impl Number for $t {
305 const ZERO: Self = 0.0;
306 const ONE: Self = 1.0;
307 const MIN: Self = Self::NEG_INFINITY;
308 const MAX: Self = Self::INFINITY;
309
310 #[inline]
311 fn abs(self) -> Self {
312 self.abs()
313 }
314
315 #[inline]
316 fn rem_euclid(self, rhs: Self) -> Self {
317 self.rem_euclid(rhs)
318 }
319
320 #[inline]
321 fn squared_diff(self, rhs: Self) -> Self {
322 let diff = self - rhs;
323 diff * diff
324 }
325 }
326
327 impl Signed for $t {
328 const MINUS_ONE: Self = -Self::ONE;
329 }
330 )+};
331}
332number_impl! {int => u8: i8, u16: i16, u32: i32, u64: i64, u128: i128, usize: isize}
333number_impl! {float => f32, f64}
334
335#[inline]
347#[must_use]
348pub fn is_prime<T: UnsignedInteger>(n: T) -> bool {
349 if n <= T::ONE {
350 return false;
351 }
352 if n == T::from(2) || n == T::from(3) {
353 return true;
354 }
355 if n % T::from(2) == T::ZERO || n % T::from(3) == T::ZERO {
356 return false;
357 }
358
359 let mut i = T::from(5);
360 while let Some(square) = i.checked_mul(i)
361 && square <= n
362 {
363 if n % i == T::ZERO || n % (i + T::from(2)) == T::ZERO {
364 return false;
365 }
366
367 if let Some(next) = i.checked_add(T::from(6)) {
368 i = next;
369 } else {
370 break;
371 }
372 }
373
374 true
375}
376
377#[inline]
391#[must_use]
392pub fn sum_of_divisors<T: UnsignedInteger>(n: T) -> Option<T> {
393 if n <= T::ONE {
394 return Some(n);
395 }
396
397 let mut sum = T::ZERO;
398 let mut d = T::ONE;
399 while let Some(square) = d.checked_mul(d)
400 && square <= n
401 {
402 if n % d == T::ZERO {
403 sum = sum.checked_add(d)?;
404
405 let q = n / d;
406 if q != d {
407 sum = sum.checked_add(q)?;
408 }
409 }
410
411 d += T::ONE;
412 }
413
414 Some(sum)
415}
416
417#[inline]
426#[must_use]
427pub fn gcd<T: Integer>(mut a: T, mut b: T) -> T {
428 while b != T::ZERO {
429 (a, b) = (b, a % b);
430 }
431 a
432}
433
434#[inline]
448#[must_use]
449pub fn egcd<T: SignedInteger>(mut a: T, mut b: T) -> (T, T, T) {
450 let (mut x0, mut x1, mut y0, mut y1) = (T::ONE, T::ZERO, T::ZERO, T::ONE);
451
452 while b != T::ZERO {
453 let q = a / b;
454 (a, b) = (b, a % b);
455 (x0, x1) = (x1, x0 - q * x1);
456 (y0, y1) = (y1, y0 - q * y1);
457 }
458
459 (a, x0, y0)
460}
461
462#[inline]
471#[must_use]
472pub fn lcm<T: Integer>(a: T, b: T) -> T {
473 if a == T::ZERO || b == T::ZERO {
474 return T::ZERO;
475 }
476
477 (a / gcd(a, b)).abs() * b.abs()
478}
479
480#[inline]
494#[must_use]
495pub fn mod_inverse<T: SignedInteger>(a: T, b: T) -> Option<T> {
496 let (gcd, x, _) = egcd(a, b);
497 if gcd == T::ONE {
498 Some(x.rem_euclid(b))
499 } else {
500 None
501 }
502}
503
504#[inline]
518#[must_use]
519pub fn chinese_remainder<T: SignedInteger>(
520 residues: impl IntoIterator<Item = T>,
521 moduli: impl IntoIterator<Item = T, IntoIter: Clone>,
522) -> Option<T> {
523 let moduli = moduli.into_iter();
524 let product = moduli.clone().product();
525
526 let mut sum = T::ZERO;
527 for (residue, modulus) in residues.into_iter().zip(moduli) {
528 let p = product / modulus;
529 sum += residue * mod_inverse(p, modulus)? * p;
530 }
531
532 Some(sum.rem_euclid(product))
533}
534
535#[inline]
544#[must_use]
545pub fn mod_pow<T: UnsignedInteger>(base: T, exponent: T, modulus: T) -> T {
546 let mut result = T::ONE;
547 let mut base = base % modulus;
548 let mut exponent = exponent;
549
550 while exponent > T::ZERO {
551 if exponent % T::from(2) == T::ONE {
552 result = (result * base) % modulus;
553 }
554 exponent >>= 1;
555 base = (base * base) % modulus;
556 }
557
558 result
559}