杜教筛之逆运算

· · 个人记录

前言：

下面介绍的这种方法并不常见，但是非常的有用
准确来说，我是来拓荒的，所以有什么问题请一定指出

前置技能：

积性函数
狄利克雷卷积
一定式子转化能力

其实对杜教筛知识点方面要求并不是很高

简单介绍几种常用积性函数：

1.\text{欧拉函数：}\phi(x)=\text{ 1—x与x互质的数的个数} 2.\text{莫比乌斯函数：}\mu(x)\text{ 这个函数定义难以描述，可以自行查找} 3.\text{约数个数：}d(x)=\sum_{d|x}1 4.\text{约数和：}\sigma(x)=\sum_{d|x}d 5.\text{恒等函数：}I(x)=1 6.\text{单元函数：}id(x)=x 7.\text{元函数：}\epsilon(x)=[x=1]

狄利克雷卷积（*）

对于两个数论函数 f(x),g(x)
它们的卷积形式为： f*g(x)=\sum_{d|x}f(d)\times g(\frac{x}{d})

卷积满足
交换律： f*g(x)=g*f(x)
结合律： (f*g)*h(x)=f*(g*h)(x)
分配律： (f+g)*h(x)=f*h(x)+g*h(x)

且 积性函数*积性函数 为 积性函数

牢记下面公式：
d(x)=I*I(x) \sigma(x)=I*id(x) id(x)=I*\phi(x) \epsilon(x)=I*\mu(x) f*\epsilon(x)=f(x)

进入正题：

首先介绍杜教筛的式子：

杜教筛之所以是杜教筛，因为存在这样的式子：

\sum_{i=1}^nf*g(i)=\sum_{i=1}^nf(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}g(j)

证明：

\sum_{i=1}^nf*g(i)=\sum_{i=1}^n\sum_{d|i}f(\frac id)g(d) =\sum_{i=1}^n\sum_{d=1}f(d)g(\frac id)[d|i] =\sum_{d=1}^nf(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}g(i)
引入：

考虑这样一道题：

\sum_{i=1}^ni\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}\mu(j)

常见做法：
预处理\mu(x)前缀和，然后整除分块，时间复杂度O(T\sqrt n+n)

但是若T\le10^7,n\le10^7,妥妥的TLE
观察杜教筛的式子，发现

\sum_{i=1}^ni\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}\mu(j)=\sum_{i=1}^nid*\mu(i)=\sum_{i=1}^n\phi(i)

也就是说此式子与\phi(x)前缀和等价
那么我们只用预处理\phi(x)前缀和，O(1)回答询问即可，时间复杂度O(T+n)

这就是杜教筛逆运算最基础的应用

进阶应用1：

考虑这样一道题：

\sum_{i=1}^n\lfloor\frac ni\rfloor\mu*\phi(i)

常见做法：
积性函数筛，筛出\mu*\phi(x)\ O(n\log\log n)并求前缀和
对于每次询问，整除分块
时间复杂度O(n\log\log n+T\sqrt n)

同样的若T\le 10^7,n\le10^7,妥妥的TLE
此时又来观察杜教筛式子，如果我们把g(x)函数特殊化为I(x)=1，可以得到

\sum_{i=1}^nI*f(i)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor f(i)

把f(x)替换为\mu*\phi(x)不就是我们要求的式子吗，于是化简为

\sum_{i=1}^n\lfloor\frac ni\rfloor\mu*\phi(i)=\sum_{i=1}^nI*\mu*\phi(i)=\sum_{i=1}^n\phi(i)

那么接下来就与前一道相同了，时间复杂度O(T+n)

进阶应用2：

考虑这样一道题：

\sum_{i=1}^n\lfloor\frac ni\rfloor^2\mu(i)

好像很熟悉的亚子。。。
常见做法：
处理\mu(x)前缀和，整除分块，时间复杂度O(n+T\sqrt n)

然后被T\le 10^7,n\le10^7毒瘤数据卡死

然而继续观察杜教筛式子，把g(x)函数特殊化为id(x)=x，可以得到

\sum_{i=1}^nid*f(i)=\sum_{i=1}^nf(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}id(j) =\sum_{i=1}^nf(i)\frac{\lfloor\frac{n}{i}\rfloor\times(\lfloor\frac{n}{i}\rfloor+1)}{2} =\frac{\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor^2 f(i)+\sum_{i=1}^nI*f(i)}{2}

移项得

\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor^2 f(i)=2\times\sum_{i=1}^nid*f(i)-\sum_{i=1}^nI*f(i)

将f(x)替换为\mu(x),得

\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor^2 \mu(i)=2\times\sum_{i=1}^n\phi(i)-1

那么接下来就与前两道相同了，时间复杂度O(T+n)

当然你要这么做我也没办法：

\sum_{i=1}^n\lfloor\frac ni\rfloor^2\mu(i)=\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=1]=2\times\sum_{i=1}^n\phi(i)-1
总结：

总而言之，三个式子比较重要

1.\sum_{i=1}^nf(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}g(j)=\sum_{i=1}^nf*g(i) 2.\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor f(i)=\sum_{i=1}^nI*f(i) 3.\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor^2 f(i)=2\times\sum_{i=1}^nid*f(i)-\sum_{i=1}^nI*f(i)

后记：

可以看看这篇题解，应该会对此方法有更好理解

因为网络上暂时还没找到过这种方法，所以以上全是博主yy出来的
有木有用请由自己掂量，有错误请一定指出
关于这种方法有新的拓展也请一定提出