Function pow_root_raw 

fn pow_root_raw<const P: u32>(exp: u32, pow_lo: &[u32], pow_hi: &[u32]) -> u32

Examples found in repository

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

    pub fn pow_root_reduced(&self, exp_mod: u32) -> u32 {
        assert!(exp_mod < P - 1);
        pow_root_raw::<P>(exp_mod, &self.pow_lo, &self.pow_hi)
    }

    #[inline]
    fn log_r(&self, x: u32) -> u32 {
        let (i, b) = self.small_fraction(x);
        let k = table_k::<P>();
        let ord = P - 1;
        self.log[i] + ord - self.log[k + b as usize]
    }
}

impl<const P: u32, const BUILD_INV: bool, const BUILD_POW: bool> Default
    for FastPrimeMod<P, BUILD_INV, BUILD_POW>
{
    fn default() -> Self {
        Self::new()
    }
}

fn build_pow<const P: u32>(root: u32) -> (Box<[u32]>, Box<[u32]>) {
    let mut pow_lo = vec![0; POW_BLOCK + 1].into_boxed_slice();
    let mut pow_hi = vec![0; POW_BLOCK + 1].into_boxed_slice();
    pow_lo[0] = 1;
    pow_hi[0] = 1;
    for i in 0..POW_BLOCK {
        pow_lo[i + 1] = mul_mod_raw::<P>(pow_lo[i], root);
    }
    let block_power = pow_lo[POW_BLOCK];
    for i in 0..POW_BLOCK {
        pow_hi[i + 1] = mul_mod_raw::<P>(pow_hi[i], block_power);
    }
    (pow_lo, pow_hi)
}

fn build_inv<const P: u32>() -> Box<[u32]> {
    let k = table_k::<P>();
    let mut inv = vec![0; table_len::<P>()].into_boxed_slice();
    inv[k + 1] = 1;
    for i in 2..=k {
        let q = P.div_ceil(i as u32);
        let r = i as u32 * q - P;
        inv[k + i] = mul_mod_raw::<P>(inv[k + r as usize], q);
    }
    for i in 1..=k {
        inv[k - i] = P - inv[k + i];
    }
    inv
}

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
}