Struct U32Map 

struct U32Map {
    keys: Box<[u32]>,
    values: Box<[u32]>,
    mask: usize,
}

Fields

keys: Box<[u32]>

values: Box<[u32]>

mask: usize

Implementations

impl U32Map

fn new(capacity: usize) -> Self

Examples found in repository

crates/competitive/src/math/fast_prime_mod.rs (line 248)

fn build_log<const P: u32>(root: u32, pow_lo: &[u32], pow_hi: &[u32]) -> Box<[u32]> {
    let k = table_k::<P>();
    let ord = P - 1;
    let mut lpf = vec![0; k + 1].into_boxed_slice();
    let mut primes = vec![];
    lpf[1] = 1;
    for i in 2..=k {
        if lpf[i] == 0 {
            lpf[i] = i as u32;
            primes.push(i as u32);
        }
        for &p in primes.iter() {
            let p = p as usize;
            if p > lpf[i] as usize || p > k / i {
                break;
            }
            lpf[i * p] = p as u32;
        }
    }

    let baby_size = (BSGS_SIZE as u32).min(ord);
    let mut baby = U32Map::new(baby_size as usize);
    let mut pw = 1;
    for i in 0..baby_size {
        baby.insert(pw, i);
        pw = mul_mod_raw::<P>(pw, root);
    }
    let q = pow_root_raw::<P>(ord - baby_size, pow_lo, pow_hi);

    let mut log = vec![0; table_len::<P>()].into_boxed_slice();
    log[k + 1] = 0;
    let mut rng = Xorshift::default();
    let small_primes = [2, 3, 5, 7, 11, 13, 17, 19];
    for i in 2..=k {
        let p = lpf[i] as usize;
        if p < i {
            log[k + i] = add_mod(log[k + p], log[k + i / p], ord);
        } else if i < 100 {
            let mut x = i as u32;
            let mut ans = 0;
            loop {
                if let Some(v) = baby.get(x) {
                    log[k + i] = ans + v;
                    break;
                }
                ans += baby_size;
                x = mul_mod_raw::<P>(x, q);
            }
        } else if i > P as usize / i {
            let j = (P as usize) / i;
            let r = (P as usize) % i;
            let x = add_mod(log[k + r], ord / 2, ord);
            let y = log[k + j];
            log[k + i] = if x >= y { x - y } else { x + ord - y };
        } else {
            loop {
                let exp = rng.rand(ord as u64) as u32;
                let mut ans = if exp == 0 { 0 } else { ord - exp };
                let mut x = mul_mod_raw::<P>(i as u32, pow_root_raw::<P>(exp, pow_lo, pow_hi));
                for q in small_primes {
                    while x.is_multiple_of(q) {
                        x /= q;
                        ans = add_mod(ans, log[k + q as usize], ord);
                    }
                }
                if x as usize >= k {
                    continue;
                }
                while (i as u32) < x && lpf[x as usize] < i as u32 {
                    let q = lpf[x as usize];
                    x /= q;
                    ans = add_mod(ans, log[k + q as usize], ord);
                }
                if 1 < x && x < i as u32 {
                    ans = add_mod(ans, log[k + x as usize], ord);
                    x = 1;
                }
                if x == 1 {
                    log[k + i] = ans;
                    break;
                }
            }
        }
    }
    for i in 1..=k {
        log[k - i] = add_mod(log[k + i], ord / 2, ord);
    }
    log
}

fn insert(&mut self, key: u32, value: u32)

Examples found in repository

crates/competitive/src/math/fast_prime_mod.rs (line 251)

fn build_log<const P: u32>(root: u32, pow_lo: &[u32], pow_hi: &[u32]) -> Box<[u32]> {
    let k = table_k::<P>();
    let ord = P - 1;
    let mut lpf = vec![0; k + 1].into_boxed_slice();
    let mut primes = vec![];
    lpf[1] = 1;
    for i in 2..=k {
        if lpf[i] == 0 {
            lpf[i] = i as u32;
            primes.push(i as u32);
        }
        for &p in primes.iter() {
            let p = p as usize;
            if p > lpf[i] as usize || p > k / i {
                break;
            }
            lpf[i * p] = p as u32;
        }
    }

    let baby_size = (BSGS_SIZE as u32).min(ord);
    let mut baby = U32Map::new(baby_size as usize);
    let mut pw = 1;
    for i in 0..baby_size {
        baby.insert(pw, i);
        pw = mul_mod_raw::<P>(pw, root);
    }
    let q = pow_root_raw::<P>(ord - baby_size, pow_lo, pow_hi);

    let mut log = vec![0; table_len::<P>()].into_boxed_slice();
    log[k + 1] = 0;
    let mut rng = Xorshift::default();
    let small_primes = [2, 3, 5, 7, 11, 13, 17, 19];
    for i in 2..=k {
        let p = lpf[i] as usize;
        if p < i {
            log[k + i] = add_mod(log[k + p], log[k + i / p], ord);
        } else if i < 100 {
            let mut x = i as u32;
            let mut ans = 0;
            loop {
                if let Some(v) = baby.get(x) {
                    log[k + i] = ans + v;
                    break;
                }
                ans += baby_size;
                x = mul_mod_raw::<P>(x, q);
            }
        } else if i > P as usize / i {
            let j = (P as usize) / i;
            let r = (P as usize) % i;
            let x = add_mod(log[k + r], ord / 2, ord);
            let y = log[k + j];
            log[k + i] = if x >= y { x - y } else { x + ord - y };
        } else {
            loop {
                let exp = rng.rand(ord as u64) as u32;
                let mut ans = if exp == 0 { 0 } else { ord - exp };
                let mut x = mul_mod_raw::<P>(i as u32, pow_root_raw::<P>(exp, pow_lo, pow_hi));
                for q in small_primes {
                    while x.is_multiple_of(q) {
                        x /= q;
                        ans = add_mod(ans, log[k + q as usize], ord);
                    }
                }
                if x as usize >= k {
                    continue;
                }
                while (i as u32) < x && lpf[x as usize] < i as u32 {
                    let q = lpf[x as usize];
                    x /= q;
                    ans = add_mod(ans, log[k + q as usize], ord);
                }
                if 1 < x && x < i as u32 {
                    ans = add_mod(ans, log[k + x as usize], ord);
                    x = 1;
                }
                if x == 1 {
                    log[k + i] = ans;
                    break;
                }
            }
        }
    }
    for i in 1..=k {
        log[k - i] = add_mod(log[k + i], ord / 2, ord);
    }
    log
}

fn get(&self, key: u32) -> Option<u32>

Examples found in repository

crates/competitive/src/math/fast_prime_mod.rs (line 268)

fn build_log<const P: u32>(root: u32, pow_lo: &[u32], pow_hi: &[u32]) -> Box<[u32]> {
    let k = table_k::<P>();
    let ord = P - 1;
    let mut lpf = vec![0; k + 1].into_boxed_slice();
    let mut primes = vec![];
    lpf[1] = 1;
    for i in 2..=k {
        if lpf[i] == 0 {
            lpf[i] = i as u32;
            primes.push(i as u32);
        }
        for &p in primes.iter() {
            let p = p as usize;
            if p > lpf[i] as usize || p > k / i {
                break;
            }
            lpf[i * p] = p as u32;
        }
    }

    let baby_size = (BSGS_SIZE as u32).min(ord);
    let mut baby = U32Map::new(baby_size as usize);
    let mut pw = 1;
    for i in 0..baby_size {
        baby.insert(pw, i);
        pw = mul_mod_raw::<P>(pw, root);
    }
    let q = pow_root_raw::<P>(ord - baby_size, pow_lo, pow_hi);

    let mut log = vec![0; table_len::<P>()].into_boxed_slice();
    log[k + 1] = 0;
    let mut rng = Xorshift::default();
    let small_primes = [2, 3, 5, 7, 11, 13, 17, 19];
    for i in 2..=k {
        let p = lpf[i] as usize;
        if p < i {
            log[k + i] = add_mod(log[k + p], log[k + i / p], ord);
        } else if i < 100 {
            let mut x = i as u32;
            let mut ans = 0;
            loop {
                if let Some(v) = baby.get(x) {
                    log[k + i] = ans + v;
                    break;
                }
                ans += baby_size;
                x = mul_mod_raw::<P>(x, q);
            }
        } else if i > P as usize / i {
            let j = (P as usize) / i;
            let r = (P as usize) % i;
            let x = add_mod(log[k + r], ord / 2, ord);
            let y = log[k + j];
            log[k + i] = if x >= y { x - y } else { x + ord - y };
        } else {
            loop {
                let exp = rng.rand(ord as u64) as u32;
                let mut ans = if exp == 0 { 0 } else { ord - exp };
                let mut x = mul_mod_raw::<P>(i as u32, pow_root_raw::<P>(exp, pow_lo, pow_hi));
                for q in small_primes {
                    while x.is_multiple_of(q) {
                        x /= q;
                        ans = add_mod(ans, log[k + q as usize], ord);
                    }
                }
                if x as usize >= k {
                    continue;
                }
                while (i as u32) < x && lpf[x as usize] < i as u32 {
                    let q = lpf[x as usize];
                    x /= q;
                    ans = add_mod(ans, log[k + q as usize], ord);
                }
                if 1 < x && x < i as u32 {
                    ans = add_mod(ans, log[k + x as usize], ord);
                    x = 1;
                }
                if x == 1 {
                    log[k + i] = ans;
                    break;
                }
            }
        }
    }
    for i in 1..=k {
        log[k - i] = add_mod(log[k + i], ord / 2, ord);
    }
    log
}

fn index(&self, key: u32) -> usize

Examples found in repository

crates/competitive/src/math/fast_prime_mod.rs (line 383)

    fn insert(&mut self, key: u32, value: u32) {
        debug_assert_ne!(key, 0);
        let mut i = self.index(key);
        while self.keys[i] != 0 && self.keys[i] != key {
            i = (i + 1) & self.mask;
        }
        self.keys[i] = key;
        self.values[i] = value;
    }

    fn get(&self, key: u32) -> Option<u32> {
        debug_assert_ne!(key, 0);
        let mut i = self.index(key);
        while self.keys[i] != 0 {
            if self.keys[i] == key {
                return Some(self.values[i]);
            }
            i = (i + 1) & self.mask;
        }
        None
    }