筛法笔记

【杜教筛】

可以对任意数论函数 \(f\) 求前缀和，\(O(n^{\frac{2}{3}})\)。

思想：对 \(\sum (f*g)(i)\) 交换求和顺序。

记 \(S(n)=\sum_{i=1}^n f(i)\)。对于数论函数 \(g\)：\(\sum_{i=1}^n (f*g)(i)=\sum_{d=1}^ng(d)\sum_{j=1}^{[n/d]}f(j)=\sum_{d=1}^n g(d)S([n/d])\)。

注意第一项有个 \(g(1)S(n)\)，从这里面取 \(S(n)\) 求。即：\(g(1)S(n)=\sum (f*g)(i)-\sum_{d\ge 2}g(d)S([n/d])\)。

考虑构造 \(g\) 使得 \((f*g)\) 的前缀和好求。而后面那一坨可以整除分块。直接做复杂度 \(O(n^{\frac{3}{4}})\)，但如果预处理前 \(O(n^{\frac{2}{3}})\) 个位置的 \(S\) 就可以优化到 \(O(n^{\frac{2}{3}})\)。实现时可能需要用 map 对算过的 \(S\) 记忆化。

例： \(f=\mu\)。

因为 \(\mu * 1=\varepsilon\) 的前缀和始终为 \(1\)，是好求的，令 \(g=1\) 即可。

例：\(f=\varphi\)。

因为 \(\varphi * 1 = id\) 的前缀和为 \(\frac{n(n+1)}{2}\) 是好求的，令 \(g=1\) 即可。

技巧：杜教筛点乘完全积性函数。

对于 \(f\)，我们构造了一个 \(g\) 使得 \(f*g\) 的前缀和好求。那如果数论函数 \(C\) 是完全积性函数，对 \(f\cdot C\) 我们可以简单地构造 \(g'=g\cdot C\)，这样新的 \(f*g'\) 是旧的 \(f*g\) 点乘 \(C\)。

这是因为 \((f\cdot C)*(g\cdot C)=(f*g)\cdot C\)。

例：\(f=\mu \cdot id_k\)，其中 \(id_k(n)=n^k\)。

取 \(g=id_k\) 即可。

总结：只要能构造出来，就可以求任意数论函数的前缀和。构造的函数 \(g\) 需要让 \(f*g\) 的前缀和好求。

【Powerful Number 筛】

可以求积性函数的前缀和。

把所有质因子的次数都大于 \(1\) 的数称作 Powerful Number。

思想：Powerful Number 包含平方因子，所以 \(1\sim n\) 内最多只有 \(O(\sqrt n)\) 个 PN。这时我们再让质数位置的函数值都是 \(0\)，根据积性函数性质知道所有非 PN 位置都是 \(0\)，所以只需要关注 \(O(\sqrt n)\) 个位置即可。

要对积性函数 \(f\) 求前缀和。

第一步，我们先构造一个积性函数 \(g\)，要求容易求 \(g\) 的前缀和，且对所有质数位置 \(p\) 都有 \(g(p)=f(p)\)。再构造一个函数 \(h\) 使得 \(g*h=f\)，因为积性函数的逆元和卷积还是积性函数，可知 \(h=f*g^{-1}\) 也是积性函数，所以 \(h(1)=1\)。

（事实上这一步 \(h\) 不需要构造，我们只需要保证 \(h\) 存在后面就能做了。而 \(f,g\) 都是积性函数所以 \(h\) 显然存在）

那么 \(f(p)=g(1)h(p)+g(p)h(1)=h(p)+g(p)\)，故 \(h(p)=0\)，即 \(h\) 里所有质数位置都是 \(0\)。又 \(h\) 是积性函数，可知 \(h\) 所有包含一次质因子的位置都是 \(0\)，所以 \(h\) 只有在 PN 的位置非 \(0\)。

先求出 \(1\sim n\) 内所有 PN：先筛出 \(\sqrt n\) 内的所有质数，再 DFS 枚举每个质数的质数即可。记 \(G\) 为 \(g\) 的前缀和。

\[\begin{aligned} \sum_{i=1}^n f(i)&=\sum_{i=1}^n (g*h)(i)\\ &=\sum_{i=1}^n \sum_{d\mid i} g(\frac{i}{d})h(d)\\ &=\sum_{d=1}^n \sum_{i=1}^{[n/d]}g(i)h(d)\\ &=\sum_{d=1}^n h(d)\sum_{i=1}^{[n/d]}g(i)\\ &=\sum_{d=1\,或\,d\in PN} h(d)\cdot G([n/d]) \end{aligned} \]

考虑如何求出 \(h(d)\)。因为 \(h\) 是积性函数，只需要求出所有 \(h(p^c)\) 就可以求出 \(h(d)\)。一种方法是直接手推出 \(h(p^c)\) 的通项公式算，另一种方法是根据 \(g*h=f\) 知道 \(f(p^c)=\sum_{i=0}^c g(p^i)h(p^{c-i})\Rightarrow g(p^0)h(p^c)=h(p^c)=f(p^c)-\sum_{i=1}^{c}g(p^i)h(p^{c-i})\)，以此枚举 \(p,c\) 递推 \(h(p^c)\)。
第二种方法泛用性更强。

考虑如何求出 \(G([n/d])\)。如果不好直接做，可以用杜教筛 \(O(n^{\frac{2}{3}})\) 做。

分析一下总共的复杂度（认为 \(h(d)\) 使用预先递推存储的方法）。

对于 \(h(d)\) 部分，\(\sqrt n\) 内有 \(O(\frac{\sqrt n}{\log n})\) 个质数，每个质数的指数至多 \(O(\log n)\)。对于一个 \(p^c\)，计算它需要 \(c-1\) 次循环，所以总共复杂度是 \(O(\frac{\sqrt n}{\log n}\cdot \log n\cdot \log n)=O(\sqrt n\log n)\)，事实上能明显感受这个上界很松。

对于 \(G([n/d])\) 部分，如果能直接求，复杂度 \(O(\sqrt n)\)；否则是杜教筛的复杂度 \(O(n^{\frac{2}{3}})\)。

所以如果要杜教筛，复杂度是 \(O(n^{\frac{2}{3}})\)；如果不用，复杂度是 \(O(\sqrt n\log n)\) 且宽松。

例：\(f\) 为积性函数，\(f(p^k)=p^k(p^k-1)\)。

取 \(g=id\cdot \varphi\) 即可。

实现细节：