浅谈筛法
Euler 筛
Eratosthenes 筛
可以证明（不是“不难证明”），Eratosthenes 筛的复杂度为 \(\Theta(n\log \log n)\)。
Dirichlet 前缀和
以 P5495 【模板】Dirichlet 前缀和 为例。
给定 \(a_1,a_2,\cdots,a_n\)，求 \(b_1,b_2,\cdots,b_n\)，满足
\[b_i=\sum_{d\mid i} a_d \]\(n\leq 2\times 10^7\)。
直接考虑 Dirichlet 前缀和。板子如下：
for (int i=1; i<=tot; ++i)
for (int j=1; j*prime[i]<=n; ++j)
a[j*prime[i]]+=a[j];
实际上是关于素数的一个高维前缀和。利用解析数论的结论不难证明时间复杂度为 \(\Theta(n\log \log n)\)。
同理我们有 Dirichlet 后缀和。
for (int i=1; i<=tot; ++i)
for (int j=n/prime[i]; j; --j)
a[j]+=a[j*prime[i]];
例题 1
给定数组 \(a_1,a_2,\cdots,a_n\)。求出 \(b_i=\sum_{k=1}^n [i\mid a_k]\)。\(n\leq 2\times 10^7\)。
Divan and Kostomuksha (hard version)
给定数列 \(a\)。可以任意重排数列，最大化
\[\sum_{i=1}^n \gcd(a_1,a_2,\cdots,a_i) \]的值。\(n\leq 2\times 10^5\)，\(1\leq a_i\leq 2\times 10^7\)。
我们有一些性质。
- 值相同的数一定放在一起。
证明显然。 - 最优方案中，数列一定不增。
证明显然。
设 \(cnt_i\) 为 \(a_i\) 中 \(i\) 的倍数个数，设 \(f[i]\) 为重排后的数组最后一个数含有因数 \(i\) 的最大权值。我们有
\[f[i]=\max(f[i\cdot p_j]+i\cdot (cnt_i-cnt_{i\cdot p_j})) \]我们将 \(i\) 的倍数紧接在 \(i\cdot p_j\) 的倍数后面。接在后面的数有 \(i\cdot (cnt_i-cnt_{i\cdot p_j})\) 个，每个数贡献了 \(i\)。
注意到这是经典的 Dirichlet 后缀和的形式，时间复杂度 \(\Theta(V\log \log V)\)。
Wheel of factorization
咕咕咕。
杜教筛
杜教筛常用于求一类数论函数 \(g\) 的前缀和。要求：
- 可以构造 \(h\)，使得 \(f=g\ast h\)；
- \(f\) 的前缀和及 \(h\) 的单点易求。
需要注意的是，\(g\) 不必须是数论函数。
设 \(s(n)=\sum_{i=1}^n g(i)\)，我们将 \(f\) 的前缀和拆开。
\[\begin{aligned} \sum_{i=1}^n f(i)&=\sum_{i=1}^n \sum_{d\mid i}g(\frac{i}{d})h(d) \\ &=\sum_{d=1}^n h(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} g(i) \\ &=\sum_{d=1}^n h(d)s(\lfloor\frac{n}{d}\rfloor)\\ &=h(1)s(n)+\sum_{d=2}^n h(d)s(\lfloor\frac{n}{d}\rfloor)\\ \end{aligned} \]于是我们得到杜教筛的公式。
\[s(n)=\frac{\sum_{i=1}^n f(i)-\sum_{i=2}^n h(i)s(\lfloor\frac{n}{i}\rfloor) }{h(1)} \]\(s(\lfloor\frac{n}{i}\rfloor)\) 是相同的子问题，可以递归求解。
朴素地做可以证明是 \(\Theta(n^{\frac{3}{4}})\) 的。如果预处理出 \([1,n^{\frac{2}{3}}]\) 内的 \(g\) 的前缀和则可以做到 \(\Theta(n^{\frac{2}{3}})\)。
Min_25 筛
前置知识：P5493 质数前缀统计
记 \(\mathbb{P}\) 为素数集，\(p_i\) 为第 \(i\) 小的素数，\(S(n)=\displaystyle\sum_{p\leq n, p\in \mathbb{P}} p^k\)。求
\[\sum_{i=1}^{\lfloor\sqrt{n}\rfloor} i^2S(\lfloor\frac{n}{i}\rfloor) \]\(n\leq 4\times 10^{10}\)，对素数 \(p\) 取模。
观察到前面是经典的数论分块形式。于是问题的关键化为了求 \(S(n)\)。
设 \(g(n,i)\) 为用前 \(i\) 个素数筛过了之后的 \(S(n)\)。初始时有 \(g(n,0)=\sum_{i=2}^n i^k\)，不难利用 Lagrange 插值 \(\Theta(k)\) 求出（如果读者不会，可以阅读我写的《多项式基础》博客）。
考虑递推，我们先给出结论。
\[g(n,i)= \begin{cases} g(n,i-1)-p_i^k(g(\lfloor\frac{n}{p_i}\rfloor,i-1)-g(p_i-1,i-1)), & p_i^2\leq n\\ g(n,i-1) & p_i^2\gt n \end{cases} \] 标签：lfloor,frac,浅谈,筛法,sum,rfloor,leq,前缀 From： https://www.cnblogs.com/Starrykiller/p/18024051/sieves