杜教筛小记
杜教筛小记
对于一个函数 \(F(n)\)，要在较低时间内求前缀和 \(S_F(n)=\sum_{i=1}^nF(i)\)。
假设我们能找到一个函数 \(G(n)\) 使得 \(G(n),S_{F \oplus G}(n)\) 能在较短时间内算出。
其中 \(\oplus\) 表示狄利克雷卷积，\((F\oplus G)(n)=\sum_{d|n}F(d)G(\frac{n}{d})\)
那么就有
\[ \begin{aligned} \displaystyle S_{F\oplus G}(n)&=\sum_1^n G(i)S_F(\lfloor\frac{n}{i}\rfloor) \\ \displaystyle G(1)F(n)&=S_{F\oplus G}(n)-\sum_2^nG(i)S_F(\lfloor\frac{n}{i}\rfloor) \end{aligned} \]
这个 \(\lfloor\frac{n}{i}\rfloor\) 的个数是 \(O(\sqrt n)\) 的，数论分段求解。
由于每次从 \(2\) 开始枚举，每次子问题大小至少减半。
(然而并没有分析复杂度)
当 \(n\) 较小时可以直接预处理出来前 \(m\) 个( \(m\) 为以常数)。
不要存状态 \(\text{dp}\)，直接递归求解用
std::map 维护记录即可。
ps:实际上对于一个固定的 \(n\)，每次计算 \(x\) 的答案时，可以根据当前的 \(\lfloor \cfrac{n}{x}\rfloor\)
为状态编号，去掉了 std::map。
当 \(m=n^{\frac{2}{3}}\) 时，复杂度最优为 \(O(n^{\frac{2}{3}})\)。
例子1：
对于 \(F(n)=\mu(n)\)，求 \(S_\mu(n)\)。
由于 \(\sum_{d|n}\mu(d)=[n=1]\)。
那么就知道可以构造 \(G(n)=1\)。
则 \((F\oplus G)(n)=[n=1]\)，\(S_{F\oplus G}(n)=1\)
\(\displaystyle S_F(n)=S_{F\oplus G}(n)-\sum_2^nS_F(\lfloor\frac{n}{i}\rfloor)\)
例子1.5
\(F(n)=\mu(n)n^k\)，求 \(S_F(n)\)。
令 \(G(n)=n^k\)，则 \(\displaystyle (F\oplus G)(n)=\sum _{d|n} \mu(d)d^k (\frac{n}{d})^k=n^k\sum_{d|n} \mu(d)=[n=1]\cdot n^k\)，
\(\displaystyle S_F(n)=1-\sum_{i=2}^n i^kS_F(\lfloor \frac{n}{i}\rfloor )\)。
只要通过一些手段得到 \(i^k\) 前缀和即可。
例子2：
对于任何 \(F(n)=\sum_{d|n}\mu(d)H(\frac{n}{d})\)，其中 \(H(n)\) 前缀和可以求。
类似上面的，构造 \(G(n)=1\)。
\((F\oplus G)(n)=\sum_{d|n}H(d)\sum_{k|\frac{n}{d}}\mu(k)=H(n)\)，
\(\displaystyle S_F(n)=S_{H}(n)-\sum_2^nS_F(\lfloor\frac{n}{i}\rfloor)\)。
\[ \ \]
例子3+3.5:
\(F(n)=\varphi(n)\cdot n^k\)，求$ S_F(n)$。
性质：\(\displaystyle \sum_{d|n}\varphi(d)=n\)
原理简要证明：满足 \(\gcd(i,n)=\frac{n}{d}\) 的 \(i\) 共有 \(\varphi(d)\) 个，则累和就是枚举了所有 \(\gcd(i,n)\) 进行统计。
所以构造 \(G(n)=n^{k}\)。
\(\displaystyle (F\oplus G)(n)=\sum_{d|n}F(d)G(\frac{n}{d})=\sum_{d|n} \varphi(d)d^k(\frac{n}{d})^{k}=\sum_{d|n} \varphi(d) n^{k}=n^{k+1}\)，
同样的只需要求出：
\(\displaystyle S_{F\oplus G}(n)=\sum_{i=1}^n i^{k+1}\)，\(\displaystyle S_G(n)=\sum_{i=1}^n i^k\)。