【学习笔记】简单数论筛
前言
学了各种筛子，学会时我重拳出击，三天后我唯唯诺诺。
所以来复健。
线性筛
懂的都懂。
杜教筛
求函数 $f$ 的前缀和：
$$ S(n)=\sum_{i=1}^n f(i) $$
考虑另外一个函数 $g$，使得 $f*g$ 和 $g$ 的前缀和是容易求得的，则：
$$ \sum_{i=1}^n (f*g)(i)=\sum_{i=1}^n \sum_{d|i} f(d)g(\frac{i}{d}) $$
$$ =\sum_{d=1}^n g(d)S(n/d) $$
$$ =g(1)S(n)+\sum_{d=2}^n g(d)S(n/d) $$
因此：
$$ S(n)=\sum_{i=1}^n (f*g)(i) - \sum_{d=2}^n g(d)S(n/d) $$
整除分块，直接做是 $\mathcal{O}(n^{3\over 4})$ 的，预处理 $n^{2\over 3}$ 以内的前缀和可以做到 $\mathcal{O}(n^{2\over 3})$。注意用 unordered_map 记忆化一下。
注意杜教筛实际上并没有运用积性函数特有的性质，所以可以筛非积性函数的前缀和！
例子
1.求 $\mu$ 的前缀和。
显然 $\mu * 1=\varepsilon$，杜教筛。
2.求 $\varphi$ 的前缀和。
显然 $\varphi * 1=\text{Id}$，杜教筛。
3.求 $\sigma_0$ 的前缀和。
显然 $\sigma_0=1*1$，所以 $\sigma_0 * \mu = 1$，杜教筛。$\mu$ 可以一起杜教筛。
$\text{Powerful-Number}$ 筛
考虑求解积性函数 $f$ 的前缀和：
$$ \sum_{i=1}^n f(i) $$
找一个积性函数 $g$ 使得 $\forall p\in\mathbb{P},\ g(p)=f(p)$，且其前缀和是好求的。
考虑 $h=f/g$，这里的除法是狄利克雷除法。则 $f=g*h$。对于 $p\in \mathbb{P}$，有：
$$ f(p)=g(1)h(p)+g(p)h(1)=g(p) $$
显然 $g(1)=h(1)=1$，所以可以得到 $h(p)=0$。也就是 $h$ 在素数位置取值为 $0$。
考虑一个数字 $n=\prod_{i=1}^k p_i^{e_i}$，则 $h(n)=\prod_{i=1}^k h(p_i^{e_i})$，显然当 $h(n)\ne 0$ 的时候，有 $\forall i\in [1,k],\ e_i\ge 2$。
我们称满足上述条件的数字 $n$ 为 $\text{Powerful Number}$。可以证明 $\text{Powerful Number}$ 的个数是 $\mathcal{O}(\sqrt{n})$ 的。
则有：
$$ \sum_{i=1}^n f(i)=\sum_{i=1}^n \sum_{d|i} g(d)h(\dfrac{i}{d}) $$
$$ =\sum_{d=1}^n h(d)\sum_{i=1}^{n/d} g(i) $$
而 $h(d)$ 只在 $d$ 是 $\text{Powerful Number}$ 的时候非 $0$，所以可以变成：
$$ \sum_{d\in \text{PN}\cap [1,n]} h(d)\sum_{i=1}^{n/d}g(i) $$
后面的 $g$ 的前缀和可以 $\mathcal{O}(1)$ 或者杜教筛，前面的 $\text{Powerful Number}$ 可以暴力全部搜出来。需要注意杜教筛筛形如这种 $\left\lfloor\dfrac{n}{i}\right\rfloor$ 的东西的总复杂度都是 $\mathcal{O}(n^{2\over 3})$ 的。