Function prime_factors 

pub fn prime_factors(n: u64) -> Vec<(u64, u32)>

Examples found in repository

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

    pub fn new(modulus: u64, max_n: u64) -> Self {
        assert_ne!(modulus, 0);
        let ppbs = prime_factors(modulus)
            .into_iter()
            .map(|(p, e)| PrimePowerBinomial::new(p, e, max_n))
            .collect();
        Self { ppbs }
    }

crates/competitive/src/math/prime_factors.rs (line 114)

pub fn divisors(n: u64) -> Vec<u64> {
    let mut d = vec![1u64];
    for (p, c) in prime_factors(n) {
        let k = d.len();
        let mut acc = 1;
        for _ in 0..c {
            acc *= p;
            for i in 0..k {
                d.push(d[i] * acc);
            }
        }
    }
    d.sort_unstable();
    d
}

crates/competitive/src/math/primitive_root.rs (line 8)

pub fn primitive_root(p: u64) -> u64 {
    if p == 2 {
        return 1;
    }
    let phi = p - 1;
    let pf = prime_factors(phi);
    let br = BarrettReduction::<u128>::new(p as _);
    for g in 2..=3.min(p - 1) {
        if check_primitive_root(g, phi, &br, &pf) {
            return g;
        }
    }
    let mut rng = Xorshift::default();
    loop {
        let g = ((rng.rand64() as u128 * (p - 2) as u128) >> 64) as u64 + 2;
        if check_primitive_root(g, phi, &br, &pf) {
            return g;
        }
    }
}

crates/competitive/src/math/pow_prec.rs (line 20)

    pub fn new(a: MInt<M>) -> Self {
        let mut maxe = 0;
        let period: u64 = prime_factors(M::mod_into() as u64)
            .into_iter()
            .map(|(p, e)| {
                maxe = maxe.max(e);
                p.pow(e - 1) * (p - 1)
            })
            .product();
        let period = period as usize;
        let sqn = ((period as f64).sqrt() as usize).max(maxe as usize) + 1;
        let mut p0 = Vec::with_capacity(sqn);
        let mut p1 = Vec::with_capacity(sqn);
        let mut acc = MInt::<M>::one();
        for _ in 0..sqn {
            p0.push(acc);
            acc *= a;
        }
        let b = acc;
        acc = MInt::<M>::one();
        for _ in 0..sqn {
            p1.push(acc);
            acc *= b;
        }
        Self {
            period,
            sqn,
            p0,
            p1,
        }
    }

crates/competitive/src/math/discrete_logarithm.rs (line 434)

fn discrete_logarithm_prime_power(a: u64, b: u64, p: u64, e: u32) -> Option<(u64, u64)> {
    assert_ne!(p, 0);
    assert_ne!(e, 0);
    let n = p.pow(e);
    assert!(a < n);
    assert!(b < n);
    assert_eq!(gcd(a, p), 1);
    if p == 1 {
        return Some((0, 1));
    }
    if a == 0 {
        return if b == 0 { Some((1, 1)) } else { None };
    }
    if b == 0 {
        return None;
    }
    if e == 1 {
        return IC.with(|ic| unsafe { &mut *ic.get() }.discrete_logarithm(a, b, p));
    }
    let br = BarrettReduction::<u128>::new(n as _);
    if p == 2 {
        if e >= 3 {
            if a % 4 == 1 && b % 4 != 1 {
                return None;
            }
            let aa = if a % 4 == 1 { a } else { n - a };
            let bb = if b % 4 == 1 { b } else { n - b };
            let g = 5;
            let ord = n / 4;
            let x = pohlig_hellman_prime_power_order(g, aa, n, p, e - 2)?;
            let y = pohlig_hellman_prime_power_order(g, bb, n, p, e - 2)?;
            let t = solve_linear_congruence(x, y, ord)?;
            match (a % 4 == 1, b % 4 == 1) {
                (true, true) => Some(t),
                (false, true) if t.0 % 2 == 0 => Some((t.0, lcm(t.1, 2))),
                (false, false) if t.0 % 2 == 1 => Some((t.0, lcm(t.1, 2))),
                (false, false) if a == b => Some((1, lcm(t.1, 2))),
                _ => None,
            }
        } else if a == 1 {
            if b == 1 { Some((0, 1)) } else { None }
        } else {
            assert_eq!(a, 3);
            if b == 1 {
                Some((0, 2))
            } else if b == 3 {
                Some((1, 2))
            } else {
                None
            }
        }
    } else {
        let ord = n - n / p;
        let pf_ord = prime_factors(ord);
        let g = (2..)
            .find(|&g| check_primitive_root(g, ord, &br, &pf_ord))
            .unwrap();
        let mut pf_p = prime_factors(p - 1);
        pf_p.push((p, e - 1));
        let mut abm = vec![];
        for (q, c) in pf_p {
            let m = q.pow(c);
            let d = ord / m;
            let gg = pow(g, d, &br);
            let aa = pow(a, d, &br);
            let bb = pow(b, d, &br);
            let x = pohlig_hellman_prime_power_order(gg, aa, n, q, c)?;
            let y = pohlig_hellman_prime_power_order(gg, bb, n, q, c)?;
            abm.push((x, y, m));
        }
        solve_linear_congruences(abm)
    }
}

/// a^x ≡ b (mod n)
pub fn discrete_logarithm(a: u64, b: u64, n: u64) -> Option<u64> {
    let a = a % n;
    let b = b % n;
    let d = 2.max(64 - n.leading_zeros() as u64);
    let mut pw = 1 % n;
    for i in 0..d {
        if pw == b {
            return Some(i);
        }
        pw = (pw as u128 * a as u128 % n as u128) as u64;
    }
    let g = gcd(pw, n);
    if !b.is_multiple_of(g) {
        return None;
    }
    let n = n / g;
    let b = (b as u128 * modinv(pw, n) as u128 % n as u128) as u64;
    let pf = prime_factors(n);
    let mut abm = vec![];
    for (p, e) in pf {
        let q = p.pow(e);
        let x = discrete_logarithm_prime_power(a % q, b % q, p, e)?;
        abm.push((1, x.0, x.1));
    }
    solve_linear_congruences(abm).map(|x| x.0 + d)
}