Trait Unsigned

Source

pub trait Unsigned: IntBase {
    type Signed: Signed<Unsigned = Self>;

Show 14 methods    // Required methods
    fn signed(self) -> Self::Signed;
    fn abs_diff(self, other: Self) -> Self;
    fn div_ceil(self, rhs: Self) -> Self;
    fn is_power_of_two(self) -> bool;
    fn next_power_of_two(self) -> Self;
    fn is_multiple_of(self, rhs: Self) -> bool;
    fn next_multiple_of(self, rhs: Self) -> Self;
    fn gcd(self, other: Self) -> Self;
    fn mod_add(self, rhs: Self, modulo: Self) -> Self;
    fn mod_sub(self, rhs: Self, modulo: Self) -> Self;
    fn mod_mul(self, rhs: Self, modulo: Self) -> Self;

    // Provided methods
    fn lcm(self, other: Self) -> Self { ... }
    fn mod_inv(self, modulo: Self) -> Self { ... }
    fn mod_neg(self, modulo: Self) -> Self { ... }
}

Expand description

Trait for unsigned integer operations.

Required Associated Types§

Source

type Signed: Signed<Unsigned = Self>

Required Methods§

Source

fn mod_mul(self, rhs: Self, modulo: Self) -> Self

Provided Methods§

Source

fn lcm(self, other: Self) -> Self

Source

fn mod_inv(self, modulo: Self) -> Self

Examples found in repository ?

crates/competitive/src/math/linear_congruence.rs (line 15)

6pub fn solve_linear_congruence<T>(a: T, b: T, m: T) -> Option<(T, T)>
7where
8    T: Unsigned,
9{
10    let g = a.gcd(m);
11    if b % g != T::zero() {
12        return None;
13    }
14    let (a, b, m) = (a / g, b / g, m / g);
15    Some((b.mod_mul(a.mod_inv(m), m), m))
16}

More examples

Hide additional examples

crates/competitive/src/math/garner.rs (line 52)

39    pub fn new_unchecked<M>(moduli: M, modulo: T) -> Self
40    where
41        M: IntoIterator<Item = T>,
42    {
43        let mut moduli: Vec<_> = moduli.into_iter().collect();
44        let n = moduli.len();
45        moduli.push(modulo);
46        let coeff_len = n * (n + 1) / 2;
47        let mut coeff = Vec::with_capacity(coeff_len);
48        let mut inv = Vec::with_capacity(n);
49        let mut prefix = vec![T::one(); moduli.len()];
50        for i in 0..n {
51            let modulus = moduli[i];
52            inv.push(prefix[i].mod_inv(modulus));
53            for j in i + 1..=n {
54                coeff.push(prefix[j]);
55                prefix[j] = prefix[j].mod_mul(modulus, moduli[j]);
56            }
57        }
58        Self { moduli, coeff, inv }
59    }

crates/competitive/src/math/arbitrary_mod_binomial.rs (line 62)

44    fn new(p: u64, e: u32, max_n: u64) -> Self {
45        let m = p.checked_pow(e).expect("prime power overflow");
46        let bp = BarrettReduction::new(p);
47        let bm = BarrettReduction::new(m);
48        let bm128 = BarrettReduction::new(m as u128);
49        let size = max_n.min(m - 1);
50        assert!(size < usize::MAX as u64);
51        let size = size as usize;
52        let mut fact = vec![1u64; size + 1];
53        let mut inv_fact = vec![1u64; size + 1];
54        if m < 1 << 31 {
55            for i in 2..=size {
56                fact[i] = if bp.rem(i as u64) == 0 {
57                    fact[i - 1]
58                } else {
59                    bm.rem(fact[i - 1] * i as u64)
60                };
61            }
62            inv_fact[size] = fact[size].mod_inv(m);
63            for i in (3..=size).rev() {
64                inv_fact[i - 1] = if bp.rem(i as u64) == 0 {
65                    inv_fact[i]
66                } else {
67                    bm.rem(inv_fact[i] * i as u64)
68                };
69            }
70        } else {
71            for i in 2..=size {
72                fact[i] = if bp.rem(i as u64) == 0 {
73                    fact[i - 1]
74                } else {
75                    bm128.rem(fact[i - 1] as u128 * i as u128) as u64
76                };
77            }
78            inv_fact[size] = fact[size].mod_inv(m);
79            for i in (3..=size).rev() {
80                inv_fact[i - 1] = if bp.rem(i as u64) == 0 {
81                    inv_fact[i]
82                } else {
83                    bm128.rem(inv_fact[i] as u128 * i as u128) as u64
84                };
85            }
86        }
87        let delta = if p == 2 && e >= 3 { 1 } else { m - 1 };
88        Self {
89            p,
90            e,
91            m,
92            size,
93            fact,
94            inv_fact,
95            delta,
96            bp,
97            bm,
98            bm128,
99        }
100    }