P4213
【模板】杜教筛（Sum）
Orz _rqy。
Orz Apia Du。
不想改 int。。。所以我选择调整预处理的大小。
效果拔群。
这里简单把杜教筛的式子推一遍。
已知函数 $f$ 和 $g$。我们要求的是 $S_f$。这里 $S_f(n)=\sum_{i=1}^{n}f(i)$。
假设我们可以比较轻松地求出 $S_g$ 和 $S_{(f\ast g)}$ 及它们的前缀和。
这里 $(f\ast g)(i)=\sum_{xy=i}f(x)g(y)$（好像看杜教筛的人不会有不知道的。。。）。
先从 $f*g$ 的前缀和开始推导：
$$\sum_{i=1}^n(f\ast g)(i)=\sum_{i=1}^n\sum_{xy=i}f(x)g(y)$$
然后把 $y$ 提前枚举：
$$\sum_{i=1}^n(f\ast g)(i)=\sum_{y=1}^ng(y)\sum_{xy\le n}f(x)$$
实际上就是：
$$\sum_{i=1}^n(f\ast g)(i)=\sum_{y=1}^ng(y)\sum_{x=1}^{\lfloor\frac{n}{y}\rfloor}f(x)$$
即：
$$\sum_{i=1}^n(f\ast g)(i)=\sum_{y=1}^ng(y)S_f(\lfloor\dfrac{n}{y}\rfloor)$$
然后我们把右边除 $g(1)S_f(n)$ 的部分往另一边移：
$$g(1)S_f(n)=\sum_{i=1}^n(f\ast g)(i)-\sum_{y=2}^ng(y)S_f(\lfloor\dfrac{n}{y}\rfloor)$$
一般情况下我们找的 $g$ 是积性函数并且 $g(1)=1$，所以我们可以直接得到 $S_f(n)$ 的一个表达式。如果不是积性函数把 $g(1)$ 除过去就完了。
然后我们显然得到了一个可以递推解决的东西，这个东西很像 DP，而且后面那一部分显然可以数论分块。
所以我们可以采取类似 DP 的方式记忆化瞎搞。
主定理计算这个复杂度似乎有一点点玄学。
我们发现函数调用的 $\lfloor\dfrac{n}{y}\rfloor$（设为 $x$），分别是 $1,2,3,\cdots,\lfloor\sqrt{n}\rfloor$ 和 $\lfloor\dfrac{n}{1}\rfloor,\lfloor\dfrac{n}{2}\rfloor,\cdots,\lfloor\dfrac{n}{\sqrt{n}}\rfloor$。于是我们的复杂度就是求个和：
$$O(\sum_{i=1}^{\sqrt{n}}\sqrt{i}+\sum_{i=1}^{\sqrt{n}}\sqrt{\lfloor\dfrac{n}{i}\rfloor})=O(\int_{1}^{\sqrt{n}}x^{\frac{1}{2}}\delta x+\int_{1}^{\sqrt{n}}\sqrt{\dfrac{n}{x}}\delta x)$$
都是初等函数，直接积分：
$$O(\dfrac{2}{3}n^{\frac{3}{4}}-\dfrac{2}{3}+2n^{\frac{3}{4}}-2n^{\frac{1}{2}})=O(n^{\frac{3}{4}})$$
也就是说我们成功找到了低于线性的一种方法。
但我们不能满足于此。
发现这个东西我们可以先预处理出 $S_f$ 在 $1,2,\cdots,n^c$（$c>\dfrac{1}{2}$，其实可以尽量大，这里只是图证明省事）的值，于是函数调用的 $x$ 就是 $\lfloor\dfrac{n}{1}\rfloor,\lfloor\dfrac{n}{2}\rfloor,\cdots,\lfloor\dfrac{n}{n^{1-c}}\rfloor$。
我们再求一次和：
$$O(n^c+\sum_{i=1}^{n^{1-c}}\sqrt{\lfloor\dfrac{n}{i}\rfloor})$$
积分近似，就是：
$$O(n^c+\int_{1}^{n^{1-c}}\sqrt{\dfrac{n}{x}}\delta x)=O(n^c+n^{1-\frac{1}{2}c})$$
现在我们要求复杂度最小，所以 $c=\dfrac{2}{3}$。此时时间复杂度 $O(n^{\frac{2}{3}})$。
现在我们开始着手考虑实现这个想法。
首先这是个递归调用，还需要加记忆化。但是一个很烦人的问题就是这个记忆化的数组可能需要很大。
一个比较 naive 的方法是用 STL map，开了 O2 跑得巨快。但可惜的是理论复杂度会多一个 $\log$。
我们发现，其实真正调用的 $x$，都是一些形如 $\lfloor\dfrac{n}{y}\rfloor$ 的东西，我们已经预处理了 $y>n^{1-c}=n^{\frac{1}{3}}$ 的情况，现在调用的全部都是 $y\le n^{\frac{1}{3}}$ 的情况，也就是说，理论上需要记忆化的数组量不会超过 $n^{\frac{1}{3}}$。
让杜教筛复杂度能过的题目，其 $n$ 基本能满足 $n^{\frac{1}{3}}$ 个数组够开。
所以我们把记忆化数组的下标设为 $y$ 即可。每次调用函数的时候我们找到满足 $x=\lfloor\dfrac{n}{y}\rfloor$ 的最大的 $y$。显然 $y=\lfloor\dfrac{n}{x}\rfloor$（数论分块的一个小结论）。返回函数值的时候记忆化在这个数组中即可。
好了，讨论完杜教筛的一般套路，我们来看一看这道模板题的做法。
首先先线性筛肯定是不用说了。我们直接看这个递归怎么做：
对于求 $S_{\mu}$：
- 我们显然知道一个 $1*\mu=\varepsilon$。
- 那么设 $f=\mu$，$g=1$，就会有 $f*g=\varepsilon$。
- $1$ 和 $\varepsilon$ 的值及其前缀和实在是太好求了。
- 于是很轻松的套上了杜教筛。
给出这一部分的代码：
1
2
3
4
5
6
7
8
9inline ll SMu(ll x) {
if(x<=M) return SMu1[x];ll tmp=n/x;
if(vis[tmp]) return SMu2[tmp];
vis[tmp]=1;SMu2[tmp]=1;
for(ll i=2,j;i<=x;i=j+1) {
j=x/(x/i);SMu2[tmp]-=(j-i+1)*SMu(x/i);
}
return SMu2[tmp];
}对于求 $S_{\varphi}$：
- 首先我们知道 $\varphi*1=\operatorname{id}$。
- 我们设 $f=\varphi$，$g=1$，则 $f*g=\operatorname{id}$。
- $1$ 很好求，$\operatorname{id}$ 的值很好求，前缀和就是等差数列求和，也非常好求。
- 于是也很轻松地套上了杜教筛。
给出这一部分的代码：
1
2
3
4
5
6
7
8
9inline ll SPhi(ll x) {
if(x<=M) return SPhi1[x];ll tmp=n/x;
if(vis[tmp]) return SPhi2[tmp];
vis[tmp]=1;SPhi2[tmp]=(x+1)*x/2;
for(ll i=2,j;i<=x;i=j+1) {
j=x/(x/i);SPhi2[tmp]-=(j-i+1)*SPhi(x/i);
}
return SPhi2[tmp];
}
好了我们做完了。
那么肯定有人问如果题目没那么模板，$g$ 和 $f*g$ 不太能 $O(1)$ 求怎么办？
对于 $g$ 来说我实在是没辙，换成其它函数试试吧（因为 $g$ 要再套杜教筛一类的东西很容易复杂度爆炸）。
对于 $f\ast g$，大胆杜教筛没有问题，理论复杂度仍然是 $O(n^{2/3})$。
（算是我写得相当用心的 blog 了。。。）
代码：
1 |
|