pub fn with_prime_list<F>(max_n: u64, f: F)Examples found in repository?
crates/competitive/src/math/lcm_convolve.rs (lines 15-21)
13 pub fn zeta_transform(f: &mut [M::T]) {
14 let n = f.len().saturating_sub(1) as u64;
15 with_prime_list(n, |pl| {
16 for &p in pl.primes_lte(n).iter() {
17 for (i, j) in (0..f.len()).step_by(p as _).enumerate() {
18 f[j] = M::operate(&f[j], &f[i]);
19 }
20 }
21 })
22 }
23}
24
25impl<G> LcmConvolve<G>
26where
27 G: Group,
28{
29 /// $$f(m) = \sum_{n \mid m}h(n)$$
30 pub fn mobius_transform(f: &mut [G::T]) {
31 let n = f.len().saturating_sub(1) as u64;
32 with_prime_list(n, |pl| {
33 for &p in pl.primes_lte(n).iter() {
34 for (i, j) in (0..f.len()).step_by(p as _).enumerate().rev() {
35 f[j] = G::rinv_operate(&f[j], &f[i]);
36 }
37 }
38 })
39 }More examples
crates/competitive/src/math/gcd_convolve.rs (lines 15-21)
13 pub fn zeta_transform(f: &mut [M::T]) {
14 let n = f.len().saturating_sub(1) as u64;
15 with_prime_list(n, |pl| {
16 for &p in pl.primes_lte(n).iter() {
17 for (i, j) in (0..f.len()).step_by(p as _).enumerate().rev() {
18 f[i] = M::operate(&f[i], &f[j]);
19 }
20 }
21 })
22 }
23}
24
25impl<G> GcdConvolve<G>
26where
27 G: Group,
28{
29 /// $$f(m) = \sum_{n \mid m}h(n)$$
30 pub fn mobius_transform(f: &mut [G::T]) {
31 let n = f.len().saturating_sub(1) as u64;
32 with_prime_list(n, |pl| {
33 for &p in pl.primes_lte(n).iter() {
34 for (i, j) in (0..f.len()).step_by(p as _).enumerate() {
35 f[i] = G::rinv_operate(&f[i], &f[j]);
36 }
37 }
38 })
39 }crates/competitive/src/math/quotient_array.rs (lines 65-77)
61 pub fn lucy_dp<G>(mut self, mut mul_p: impl FnMut(T, u64) -> T) -> Self
62 where
63 G: Group<T = T>,
64 {
65 with_prime_list(self.isqrtn, |pl| {
66 for &p in pl.primes_lte(self.isqrtn) {
67 let k = self.quotient_index(p - 1);
68 let p2 = p * p;
69 for (i, q) in Self::index_iter(self.n, self.isqrtn).enumerate() {
70 if q < p2 {
71 break;
72 }
73 let diff = mul_p(G::rinv_operate(&self[q / p], &self.data[k]), p);
74 G::rinv_operate_assign(&mut self.data[i], &diff);
75 }
76 }
77 });
78 self
79 }
80
81 /// convert $\sum_{i\leq n, i\text{ is prime}} f(i)$ to $\sum_{i\leq n} f(i)$
82 pub fn min_25_sieve<R>(&self, mut f: impl FnMut(u64, u32) -> T) -> Self
83 where
84 T: Clone + One,
85 R: Ring<T = T>,
86 R::Additive: Invertible,
87 {
88 let mut dp = self.clone();
89 with_prime_list(self.isqrtn, |pl| {
90 for &p in pl.primes_lte(self.isqrtn).iter().rev() {
91 let k = self.quotient_index(p);
92 for (i, q) in Self::index_iter(self.n, self.isqrtn).enumerate() {
93 let mut pc = p;
94 if pc * p > q {
95 break;
96 }
97 let mut c = 1;
98 while q / p >= pc {
99 let x = R::mul(&f(p, c), &(R::sub(&dp[q / pc], &self.data[k])));
100 let x = R::add(&x, &f(p, c + 1));
101 dp.data[i] = R::add(&dp.data[i], &x);
102 c += 1;
103 pc *= p;
104 }
105 }
106 }
107 });
108 for x in &mut dp.data {
109 *x = R::add(x, &T::one());
110 }
111 dp
112 }