Struct QuotientArray 

pub struct QuotientArray<T> {
    n: u64,
    isqrtn: u64,
    data: Vec<T>,
}

store with index ${\lfloor\frac{n}{i}\rfloor \mid i=1,2,\ldots,n}$

Fields

n: u64

isqrtn: u64

data: Vec<T>

Implementations

impl<T> QuotientArray<T>

where T: Zero,

pub fn zeros(n: u64) -> Self

impl<T> QuotientArray<T>

pub fn index_iter(n: u64, isqrtn: u64) -> impl Iterator<Item = u64>

Examples found in repository

crates/competitive/src/math/quotient_array.rs (line 54)

    pub fn from_fn(n: u64, f: impl FnMut(u64) -> T) -> Self {
        let isqrtn = (n as f64).sqrt().floor() as u64;
        let data = Self::index_iter(n, isqrtn).map(f).collect();
        Self { n, isqrtn, data }
    }

    /// convert $\sum_{i\leq n} f(i)$ to $\sum_{i\leq n, i\text{ is prime}} f(i)$
    ///
    /// constraints: $\mathrm{mul_p}(f(x))=f(px)$
    pub fn lucy_dp<G>(mut self, mut mul_p: impl FnMut(T, u64) -> T) -> Self
    where
        G: Group<T = T>,
    {
        let max_n = self.isqrtn as u32;
        with_prime_list(max_n, |pl| {
            for p in pl.primes_lte(max_n) {
                let p = u64::from(p);
                let k = self.quotient_index(p - 1);
                let p2 = p * p;
                for (i, q) in Self::index_iter(self.n, self.isqrtn).enumerate() {
                    if q < p2 {
                        break;
                    }
                    let diff = mul_p(G::rinv_operate(&self[q / p], &self.data[k]), p);
                    G::rinv_operate_assign(&mut self.data[i], &diff);
                }
            }
        });
        self
    }

    /// convert $\sum_{i\leq n, i\text{ is prime}} f(i)$ to $\sum_{i\leq n} f(i)$
    pub fn min_25_sieve<R>(&self, mut f: impl FnMut(u64, u32) -> T) -> Self
    where
        T: Clone + One,
        R: Ring<T = T, Additive: Invertible>,
    {
        let mut dp = self.clone();
        let max_n = self.isqrtn as u32;
        with_prime_list(max_n, |pl| {
            for p in pl.primes_lte(max_n).rev() {
                let p = u64::from(p);
                let k = self.quotient_index(p);
                for (i, q) in Self::index_iter(self.n, self.isqrtn).enumerate() {
                    let mut pc = p;
                    if pc * p > q {
                        break;
                    }
                    let mut c = 1;
                    while q / p >= pc {
                        let x = R::mul(&f(p, c), &(R::sub(&dp[q / pc], &self.data[k])));
                        let x = R::add(&x, &f(p, c + 1));
                        dp.data[i] = R::add(&dp.data[i], &x);
                        c += 1;
                        pc *= p;
                    }
                }
            }
        });
        for x in &mut dp.data {
            *x = R::add(x, &T::one());
        }
        dp
    }

pub fn map<U>(&self, f: impl FnMut(&T) -> U) -> QuotientArray<U>

Examples found in repository

crates/library_checker/src/number_theory/sum_of_totient_function.rs (line 17)

pub fn sum_of_totient_function(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n: u64);
    let mut s = 1;
    let mut pp = 0;
    let mut pc = 0;
    let inv2 = M::new(2).inv();
    let qa = QuotientArray::from_fn(n, |i| [M::from(i), M::from(i) * M::from(i + 1) * inv2])
        .map(|[x, y]| [x - M::one(), y - M::one()])
        .lucy_dp::<ArrayOperation<AdditiveOperation<_>, 2>>(|[x, y], p| [x, y * M::from(p)])
        .map(|[x, y]| y - x)
        .min_25_sieve::<AddMulOperation<_>>(|p, c| {
            if pp != p || pc > c {
                pp = p;
                pc = 1;
                s = p - 1;
            }
            while pc < c {
                pc += 1;
                s *= p;
            }
            M::from(s)
        });
    pp!(qa[n]);
}

pub fn quotient_index(&self, i: u64) -> usize

Examples found in repository

crates/competitive/src/math/quotient_array.rs (line 69)

    pub fn lucy_dp<G>(mut self, mut mul_p: impl FnMut(T, u64) -> T) -> Self
    where
        G: Group<T = T>,
    {
        let max_n = self.isqrtn as u32;
        with_prime_list(max_n, |pl| {
            for p in pl.primes_lte(max_n) {
                let p = u64::from(p);
                let k = self.quotient_index(p - 1);
                let p2 = p * p;
                for (i, q) in Self::index_iter(self.n, self.isqrtn).enumerate() {
                    if q < p2 {
                        break;
                    }
                    let diff = mul_p(G::rinv_operate(&self[q / p], &self.data[k]), p);
                    G::rinv_operate_assign(&mut self.data[i], &diff);
                }
            }
        });
        self
    }

    /// convert $\sum_{i\leq n, i\text{ is prime}} f(i)$ to $\sum_{i\leq n} f(i)$
    pub fn min_25_sieve<R>(&self, mut f: impl FnMut(u64, u32) -> T) -> Self
    where
        T: Clone + One,
        R: Ring<T = T, Additive: Invertible>,
    {
        let mut dp = self.clone();
        let max_n = self.isqrtn as u32;
        with_prime_list(max_n, |pl| {
            for p in pl.primes_lte(max_n).rev() {
                let p = u64::from(p);
                let k = self.quotient_index(p);
                for (i, q) in Self::index_iter(self.n, self.isqrtn).enumerate() {
                    let mut pc = p;
                    if pc * p > q {
                        break;
                    }
                    let mut c = 1;
                    while q / p >= pc {
                        let x = R::mul(&f(p, c), &(R::sub(&dp[q / pc], &self.data[k])));
                        let x = R::add(&x, &f(p, c + 1));
                        dp.data[i] = R::add(&dp.data[i], &x);
                        c += 1;
                        pc *= p;
                    }
                }
            }
        });
        for x in &mut dp.data {
            *x = R::add(x, &T::one());
        }
        dp
    }
}

impl<T> Index<u64> for QuotientArray<T> {
    type Output = T;
    fn index(&self, i: u64) -> &Self::Output {
        unsafe { self.data.get_unchecked(self.quotient_index(i)) }
    }
}

impl<T> IndexMut<u64> for QuotientArray<T> {
    fn index_mut(&mut self, index: u64) -> &mut Self::Output {
        let i = self.quotient_index(index);
        unsafe { self.data.get_unchecked_mut(i) }
    }

pub fn from_fn(n: u64, f: impl FnMut(u64) -> T) -> Self

Examples found in repository

crates/competitive/src/math/quotient_array.rs (line 17)

    pub fn zeros(n: u64) -> Self {
        Self::from_fn(n, |_| T::zero())
    }

crates/library_checker/src/number_theory/counting_primes.rs (line 8)

pub fn counting_primes(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n: u64);
    let qa = QuotientArray::from_fn(n, |i| i as i64 - 1).lucy_dp::<AdditiveOperation<_>>(|x, _p| x);
    pp!(qa[n]);
}

crates/library_checker/src/number_theory/sum_of_totient_function.rs (line 16)

pub fn sum_of_totient_function(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n: u64);
    let mut s = 1;
    let mut pp = 0;
    let mut pc = 0;
    let inv2 = M::new(2).inv();
    let qa = QuotientArray::from_fn(n, |i| [M::from(i), M::from(i) * M::from(i + 1) * inv2])
        .map(|[x, y]| [x - M::one(), y - M::one()])
        .lucy_dp::<ArrayOperation<AdditiveOperation<_>, 2>>(|[x, y], p| [x, y * M::from(p)])
        .map(|[x, y]| y - x)
        .min_25_sieve::<AddMulOperation<_>>(|p, c| {
            if pp != p || pc > c {
                pp = p;
                pc = 1;
                s = p - 1;
            }
            while pc < c {
                pc += 1;
                s *= p;
            }
            M::from(s)
        });
    pp!(qa[n]);
}

pub fn lucy_dp<G>(self, mul_p: impl FnMut(T, u64) -> T) -> Self

where G: Group<T = T>,

convert $\sum_{i\leq n} f(i)$ to $\sum_{i\leq n, i\text{ is prime}} f(i)$

constraints: $\mathrm{mul_p}(f(x))=f(px)$

Examples found in repository

crates/library_checker/src/number_theory/counting_primes.rs (line 8)

pub fn counting_primes(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n: u64);
    let qa = QuotientArray::from_fn(n, |i| i as i64 - 1).lucy_dp::<AdditiveOperation<_>>(|x, _p| x);
    pp!(qa[n]);
}

crates/library_checker/src/number_theory/sum_of_totient_function.rs (line 18)

pub fn sum_of_totient_function(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n: u64);
    let mut s = 1;
    let mut pp = 0;
    let mut pc = 0;
    let inv2 = M::new(2).inv();
    let qa = QuotientArray::from_fn(n, |i| [M::from(i), M::from(i) * M::from(i + 1) * inv2])
        .map(|[x, y]| [x - M::one(), y - M::one()])
        .lucy_dp::<ArrayOperation<AdditiveOperation<_>, 2>>(|[x, y], p| [x, y * M::from(p)])
        .map(|[x, y]| y - x)
        .min_25_sieve::<AddMulOperation<_>>(|p, c| {
            if pp != p || pc > c {
                pp = p;
                pc = 1;
                s = p - 1;
            }
            while pc < c {
                pc += 1;
                s *= p;
            }
            M::from(s)
        });
    pp!(qa[n]);
}

pub fn min_25_sieve<R>(&self, f: impl FnMut(u64, u32) -> T) -> Self

where T: Clone + One, R: Ring<T = T, Additive: Invertible>,

convert $\sum_{i\leq n, i\text{ is prime}} f(i)$ to $\sum_{i\leq n} f(i)$

Examples found in repository

crates/library_checker/src/number_theory/sum_of_totient_function.rs (lines 20-31)

pub fn sum_of_totient_function(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n: u64);
    let mut s = 1;
    let mut pp = 0;
    let mut pc = 0;
    let inv2 = M::new(2).inv();
    let qa = QuotientArray::from_fn(n, |i| [M::from(i), M::from(i) * M::from(i + 1) * inv2])
        .map(|[x, y]| [x - M::one(), y - M::one()])
        .lucy_dp::<ArrayOperation<AdditiveOperation<_>, 2>>(|[x, y], p| [x, y * M::from(p)])
        .map(|[x, y]| y - x)
        .min_25_sieve::<AddMulOperation<_>>(|p, c| {
            if pp != p || pc > c {
                pp = p;
                pc = 1;
                s = p - 1;
            }
            while pc < c {
                pc += 1;
                s *= p;
            }
            M::from(s)
        });
    pp!(qa[n]);
}

Trait Implementations

impl<T: Clone> Clone for QuotientArray<T>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for QuotientArray<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Index<u64> for QuotientArray<T>

type Output = T

The returned type after indexing.

fn index(&self, i: u64) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> IndexMut<u64> for QuotientArray<T>

fn index_mut(&mut self, index: u64) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.