积性函数前缀和——杜教筛

背景：

这课太无聊了，太吵学不进去，干脆写博客好了。

题目:

给定一个$n$，求${\sum }_{i=1}^n\mu (i)$和${\sum }_{i=1}^n\phi (i)$。
$(1\le n\le 10^{10})$
(某些积性函数前缀和)

引言:

如果不知道什么是积性函数出门左转隔壁教室。

我们知道，$\mu$函数和$\phi$可以$o(\sqrt{n})$求单点的值。
也可以用线性筛$o(n)$预处理出多点的值。
但是显然都不够用来做这个题。

那么神奇的地方来了，这些积性函数竟然有亚线性算法求出前缀和，可能这就是数学的魅力吧。
这里我们介绍其中一个方法，杜教筛，它可以在$o(n^{\frac{3}{4}})$的复杂度内求出积性函数的前缀和。并且我们可以预处理出前$10^6$个前缀和，将它的复杂度优化到$o(n^{\frac{2}{3}})$。

正文：杜教筛

假定我们要求前缀和的函数是$f$，并令它的前缀和$S(n)={\sum }_{i=1}^{n}f(i)$。
我们找另一个函数$g$跟它卷积求前缀和。
${\sum }_{i=1}^n(f\ast g)(i)={\sum }_{i=1}^n{\sum }_{d|i}g(d)f(\frac{i}{d})$

                             $={\sum }_{d=1}^{n}g(d){\sum }_{i=1}^{\lfloor \frac{n}{d}\rfloor }f(i)$

                             $={\sum }_{d=1}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor )$

推到这里，我们发现后面这是一个明显的数论分块式子。
但是这个式子里没有$S(n)$呀，没$S(n)$我们求啥。
所以现在我们要把$S(n)$弄出来。
我们发现当$d=1$时，后面这个东西$g(1)S(\lfloor \frac{n}{1}\rfloor )=S(n)$
然后$S(n)$就来了。
$S(n)={\sum }_{d=1}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor )-{\sum }_{d=2}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor )$

          $={\sum }_{i=1}^n(f\ast g)(i)-{\sum }_{d=2}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor )$

那么后面这个式子还是一个数论分块的式子，只要我们可以快速求出$g$的前缀和，就可以快速地求出来。

所以我们需要找到一个$g$，使得$g$和$f\ast g$的前缀和都好求。

我们现在算一下复杂度，假设$g$和$f\ast g$的前缀和都可以$o(1)$求出。
那么有. 打扰了 ，反正复杂度是$o(n^{\frac{3}{4}})$，如果我们预处理出前$10^6$项，然后再加个记忆化，复杂度就变成$o(n^{\frac{2}{3}})$了。

代码略了，请读者自行编写过题。

例题1：求${\sum }_{i=1}^n\mu (i)$。

当我们考虑用杜教筛求解积性函数前缀和时，主要就是找一个$g$使得$g$和$f\ast g$的前缀和好求。
那么对于莫比乌斯函数$\mu$，我们毫无疑问是选择用$1$函数。
有$\mu \ast 1=e$。
那么$1$函数和$e$函数的前缀和就不用多说什么了。
理A。

例题2：求${\sum }_{i=1}^n\phi (i)$。

$g$仍选择用$1$函数，有$\phi \ast 1=id$。
那么$1$函数和$id$函数的前缀和也很好求。

例题3：求${\sum }_{i=1}^{n}i\phi (i)$。

我们选用$id$作为$g$函数，首先$id$函数的前缀和可以求。
${\sum }_{i=1}^n(f\ast id)(i)={\sum }_{i=1}^n{\sum }_{d|i}d\phi (d)\ast \frac{i}{d}={\sum }_{i=1}^{n}i{\sum }_{d|i}\phi (d)={\sum }_{i=1}^n{i}^2$。
其中，因为$1\ast \phi =id$，所以${\sum }_{d|i}\phi (d)=i$。

例题n+2：求${\sum }_{i=1}^n{i}^n\phi (i)$。

我们选用$i{d}^n$作为$g$函数，那么$i{d}^n$的前缀和可以求。（拉格朗日插值?）
${\sum }_{i=1}^n(f\ast id)(i)={\sum }_{i=1}^n{\sum }_{d|i}{d}^n\phi (d)\ast (\frac{i}{d}{)}^n={\sum }_{i=1}^n{i}^n{\sum }_{d|i}\phi (d)={\sum }_{i=1}^n{i}^{n+1}$。

暂时我知道就上面这些吧。