杜教筛

做题发现普通的线性筛法已经解决不了问题了,如n给到1e9 1e10 此时还有20~40分就拿不到了。

但是我们发现要求出来的某个积性函数的前缀和的个数是有限的 只要我们能快速求出某个单点处的前缀和即可.

如我们要求$\sum_{i}^{n}{f(i)}$ 我们只需求出在点n处的值即可所以我们只要在非线性的时间搞出来即可,显然题目中的n的个数也是有限个的.

注意使用杜教筛的前提是 f是一个积性函数.

我们再构造两个积性函数h和g.使得$h=f*g$;

记$S(n)=\sum_{i=1}^{n}f(i)$ 现在开始求$\sum_{i=1}^{n}{h(i)}$

$\sum_{i=1}^{n}{h(i)}=\sum_{i=1}^{n}{\sum_{d|i}{g(d)\cdot f(\frac{i}{d})}}$$\to =\sum_{d=1}^{n}g(d)\cdot\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)$

$\to \sum_{i=1}^{n}h(i)=\sum_{d=1}^{n}{g(d)}\cdot S(\lfloor\frac{n}{d}\rfloor)$

把右边第一项给提出来得到了一个杜教筛真正有用的式子.

$g(1)\cdot S(n)=\sum_{i=1}^{n}h(i)-\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)$

发现了什么？只要我们h这个函数前缀和非常的好求 并且对后面的式子进行整除分块我们就可以在较短的时间内求出S(n).

当然我们要先预处理出大概$n^{\frac{2}{3}}$这么多的前缀和再使用杜教筛此时复杂度为$n^{\frac{2}{3}}$

否则的话就是$n^{\frac{3}{4}}$当然过程中需要map来存一下值 免的重复计算会加速很多..

现在列举几个能杜教筛的式子.

1. 求$S(n)=\sum_{i=1}^{n}{\mu(i)}$

发现函数是$\mu$我们用哪一个积性函数卷一下能得到一个非常好用的h函数呢?

很自然的想到 $\sum_{d|n}{\mu(d)}=[n=1]$我们只需要卷一个$I$即可.

$I*\mu=\sum_{d|n}{\mu(d)\cdot I(\frac{n}{d})}=e(n)$

$e$函数的前缀和就是1 那么杜教筛的式子就变成了 $S(n)=1-\sum_{d=2}^{n} S(\lfloor\frac{n}{d}\rfloor)$

采用上述方法递归计算即可.

2. 求$S(n)=\sum_{i=1}^{n}{\phi(i)}$

我们联想一下$phi$这个函数有什么优美的性质没有，有的$\sum_{d|n}{\phi(d)}=n$

显然卷上$I$函数就等于$id$函数了...

杜教筛的式子为 $S(n)=sum(n)-\sum_{d=2}^{n}S(\lfloor\frac{n}{d}\rfloor)$

$sum(n)=\sum_{i=1}^{n}{i}$等差数列很好计算.带入求值即可.

3. 求$S(n)=\sum_{i=1}^{n}{i\cdot\phi(i)}$

$f(i)=i\cdot\phi(i)$ 先写出卷积的形式$\sum_{d|n}{d\cdot\phi(d)\cdot g(\frac{n}{d})}$

我们就可以很显然的选出函数$id$了

那么刚才那个卷积就变成了$\sum_{d|n}{n\cdot\phi(d)}\to n\cdot\sum_{d|n}{\phi(d)}\to n^2$

杜教筛的式子为$S(n)=\sum_{i=1}^{n}{i^2}-\sum_{d=2}^{n}{d\cdot S(\lfloor\frac{n}{d}\rfloor)}$

显然后面那个整除分块的时候再乘一个等差数列即可.考虑前面的一项怎么搞..

好尴尬..$\sum_{i=1}^{n}{i^2}$不会求...当然我们大力推式子也是能推的更简便的方法是百度一下然后记住这个式子.

有了百度上说是$\sum_{i=1}^{n}{i^2}=n(n+1)(2n+1)/6$证明比较有技巧性这里不再赘述.

所以上式也可以杜教筛了！

值得一提的是不要忽略了函数$h(i)=i^2$这个函数是一个积性函数证明的话原因是由于这是两个积性函数的卷积所以还是一个积性函数吧.

这里再写一遍基础式 因为很重要...$g(1)\cdot S(n)=\sum_{i=1}^{n}{h(i)}-\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)$

一道例题入手：[简单的数学题](https://www.luogu.com.cn/problem/P3768)(看三天的例题了 再推一边。

求$(\sum_{i=1}^{n}\sum_{i=1}^{n}{i\cdot j\cdot gcd(i,j)})\mod p$

这里我直接给出最终的式子 注意在推的时候细节别搞错！

最后推到的式子是$\sum_{T=1}^{n}{sum(\lfloor\frac{n}{T}\rfloor)^2}\cdot T^2\sum_{x|T}{\frac{T}{x}\mu(x)}$

其中$sum(n)=\sum_{i=1}{n}$前面那个完全可以数论分块的时候搞 看后面的式子如何杜教筛搞...

也就是我说我们想要在数论分块中得到$f(T)=T^2\sum_{x|T}{\frac{T}{x}\mu(x)}$

我们发现这本身就是一个类似于卷积的形式了我们不能再给它卷积了那样更筛不出来了...

卷积？没错是一个id函数和$\mu$函数的卷积再乘上了一个常数，那么显然$id*\mu=\phi$

所以$f(T)=T^2\phi(T)$再构造一个积性函数和f卷上 先把卷积的形式写出来是$h(n)=\sum_{d|n}{f(d)\cdot g(\frac{n}{d})}$

卷出的具体结果是$h(n)=\sum_{d|n}{x^2\phi(x)\cdot g(\frac{n}{d})}$

所以很显然我们构造$g(x)=x^2$那么$h(n)=n^3$

$f*h=n^3$所以现在要求的是$1^3+2^3+3^3+...n^3$的前缀和 这个东西根据小学奥数我们发现等于:$sum(n)^2$

综上我们再数论分块的时候使用杜教筛即可.时间复杂度我也不太会计算,但是需要用map来加速.

来道例题：[2020 CCPC-Wannafly Winter Camp Day3 D 求和](https://ac.nowcoder.com/acm/contest/4114/D)

题目意思很简单就是让我们推式子 下面是我推的过程.

求 $\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{i}gcd(i,j,k)$

$\sum_{d=1}^{n}d\sum_{i=1}^{n/d}\sum_{j=1}^{i}\sum_{k=1}^{i}\sum_{x|i,x|j,x|k}\mu(x)$

$\sum_{d=1}^{n}d\sum_{x=1}^{n/d}\mu(x)\sum_{i=1}^{n/xd}\sum_{j=1}^{i}\sum_{k=1}^{i}1$

$\sum_{d=1}^{n}d\sum_{x=1}^{n/d}\mu(x)\sum_{i=1}^{n/xd}i^2$

观察 $x*d<=n$ 枚举 $T=x*d而d=T/x$

$\sum_{T=1}^{n}\sum_{x|T}\mu(x)\frac{T}{x}\sum_{i=1}^{n/T}i^2$

$\sum_{T=1}^{n}\sum_{i=1}^{n/T}i^2\sum_{x|T}\mu(x)\frac{T}{x}$

因为$\sum_{x|T}\mu(x)\frac{T}{x}$=$\phi(T)$