pub fn with_prime_list<F>(max_n: u32, 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 u32;
15 with_prime_list(n, |pl| {
16 for p in pl.primes_lte(n) {
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 u32;
32 with_prime_list(n, |pl| {
33 for p in pl.primes_lte(n) {
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 u32;
15 with_prime_list(n, |pl| {
16 for p in pl.primes_lte(n) {
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 u32;
32 with_prime_list(n, |pl| {
33 for p in pl.primes_lte(n) {
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 66-79)
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 let max_n = self.isqrtn as u32;
66 with_prime_list(max_n, |pl| {
67 for p in pl.primes_lte(max_n) {
68 let p = u64::from(p);
69 let k = self.quotient_index(p - 1);
70 let p2 = p * p;
71 for (i, q) in Self::index_iter(self.n, self.isqrtn).enumerate() {
72 if q < p2 {
73 break;
74 }
75 let diff = mul_p(G::rinv_operate(&self[q / p], &self.data[k]), p);
76 G::rinv_operate_assign(&mut self.data[i], &diff);
77 }
78 }
79 });
80 self
81 }
82
83 /// convert $\sum_{i\leq n, i\text{ is prime}} f(i)$ to $\sum_{i\leq n} f(i)$
84 pub fn min_25_sieve<R>(&self, mut f: impl FnMut(u64, u32) -> T) -> Self
85 where
86 T: Clone + One,
87 R: Ring<T = T, Additive: Invertible>,
88 {
89 let mut dp = self.clone();
90 let max_n = self.isqrtn as u32;
91 with_prime_list(max_n, |pl| {
92 for p in pl.primes_lte(max_n).rev() {
93 let p = u64::from(p);
94 let k = self.quotient_index(p);
95 for (i, q) in Self::index_iter(self.n, self.isqrtn).enumerate() {
96 let mut pc = p;
97 if pc * p > q {
98 break;
99 }
100 let mut c = 1;
101 while q / p >= pc {
102 let x = R::mul(&f(p, c), &(R::sub(&dp[q / pc], &self.data[k])));
103 let x = R::add(&x, &f(p, c + 1));
104 dp.data[i] = R::add(&dp.data[i], &x);
105 c += 1;
106 pc *= p;
107 }
108 }
109 }
110 });
111 for x in &mut dp.data {
112 *x = R::add(x, &T::one());
113 }
114 dp
115 }