P4213 【模板】杜教筛（Sum） 题解数据结构与算法bifanwen的博客-

博客园同步

原题链接

前置知识：

莫比乌斯反演，线性筛，狄利克雷卷积，整除分块。

简要题意：

$T$

T 组询问，求：

$sum_{i=1}^n mu_i$

i=1∑n​μi​

$sum_{i=1}^n phi_i$

i=1∑n​ϕi​

其中，
$T leq 10$

T≤10，
$n < 2^{31}$

n<231.

首先，你需要知道这道题目的
$O(Tn sqrt{n})$

O(Tnn​) 算法，
$O(Tn)$

O(Tn) 算法，
$O(T+n)$

O(T+n) 算法。

显然，
$O(Tn sqrt{n})$

O(Tnn​) 是暴力，
$O(Tn)$

O(Tn) 是一个个筛，
$O(T+n)$

O(T+n) 是预处理 线性筛，一个都无法通过。

这题的瓶颈在于，我们 并不需要一个个求出
$mu$

μ 和
$phi$

ϕ，可以不拘泥于此。

想想：我们之前求
$sum_{i=1}^n lfloor frac{n}{i} rfloor$

∑i=1n​⌊in​⌋ 的时候，之前手玩 莫比乌斯反演 的时候，甚至有一次玩到
$6$

6 个
$sum$

∑ 还是一一解决了。走过这么多困难，切掉了这么多紫题，这一题怎么就不行了呢？

事实告诉人们，题目从来都是人做出来的。

我们考虑几个简单的卷积：

$mu * text{I} = ϵ , phi * text{I} = text{Id} , mu * text{Id} = phi$

μ∗I=ϵ,ϕ∗I=Id,μ∗Id=ϕ

好，根据这些，我们开始了伟大的探索。

假设我们要求一个 积性函数
$f$

f，可以先不直接求，搞出另一个
$g$

g，首先考虑怎么求出
$f * g$

f∗g 的前缀和，那样就可以求出
$sum_f$

∑f​.

根据 莫比乌斯反演 的性质可得：

$sum_{i=1}^n (f*g) (i)$

i=1∑n​(f∗g)(i)

$= sum_{i=1}^n sum_{d|i} f(d) times g(frac{i}{d})$

=i=1∑n​d∣i∑​f(d)×g(di​)

$= sum_{d=1}^n g(d) times sum_{i=1}^{lfloor frac{n}{d} rfloor} f(i)$

=d=1∑n​g(d)×i=1∑⌊dn​⌋​f(i)

假设
$f$

f 的前缀和为
$S$

S，则：

$= sum_{d=1}^n g(d) S(lfloor frac{n}{d} rfloor)$

=d=1∑n​g(d)S(⌊dn​⌋)

现在我们要求的是
$S(n)$

S(n).

$g(1) 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)$

g(1)S(n)=d=1∑n​g(d)S(⌊dn​⌋)−d=2∑n​g(d)S(⌊dn​⌋)

显然，因为
$g(1) S(n)$

g(1)S(n) 是
$d=1$

d=1 的答案，考虑前缀和相减即可。

此时可以得到：

$g(1) S(n) = sum_{d=1}^n (f * g) (d) – sum_{d=2}^n g(d) S(lfloor frac{n}{d} rfloor)$

g(1)S(n)=d=1∑n​(f∗g)(d)−d=2∑n​g(d)S(⌊dn​⌋)

那么显然：

$S(n) = frac{sum_{d=1}^n (f * g) (d) – sum_{d=2}^n g(d) S(lfloor frac{n}{d} rfloor)}{g(1)}$

S(n)=g(1)∑d=1n​(f∗g)(d)−∑d=2n​g(d)S(⌊dn​⌋)​

此时你会说了，好，这个式子怎么求呢？

这个式子确实难求，但关键是，
$g$

g 函数是我们自己定的，我们可以定一个
$g$

g 使得
$g$

g 和
$f*g$

f∗g 的前缀和都非常好算。

好算？联系积性函数的性质，我们想到了：
$text{I}$

I 和
$ϵ$

ϵ 都是积性函数，前缀和也非常的简单。后面一堆我们可以整除分块。

先不管怎么定
$g$

g，伪代码大概长这样：

inline ll sieve(ll n) {  ll ans=calc(n); //calc(i) 负责计算 (f*g)(i) for(ll i=2,r;i<=n;i=r+1) {   r=(n/(n/i));   ans-=(sum(r) - sum(i-1)) * sieve(n/i); //sum(i) 计算 g 的前缀和 } return ans; } 

显然你会发现，这里有递归部分。

递归？这东西，显然会把很多东西重复计算。

因此我们需要 记忆化。

到这里，杜教筛 的样子渐成，我们已经得到了其中的
$60$

60%.

下面的难点在于确定
$g$

g.

入手题目。

$f = phi$

f=ϕ，令
$g = text{I}$

g=I，则
$f * g = text{Id}$

f∗g=Id，此时可以解决。

$f = mu$

f=μ，令
$g = text{I}$

g=I，则
$f * g = ϵ$

f∗g=ϵ，此时也可以解决。

好了，现在的问题在于，这东西的时间复杂度如何？

你发现无法通过，因为，杜教筛必须要初始化一部分数据。

假设我们将
$n leq k$

n≤k 的情况的答案都初始化一遍。那么，经过分析（具体证明） 可得，这样的时间复杂度是：

$O(k + frac{n}{sqrt{k}})$

O(k+k​n​)

你会发现，只要
$O(k)$

O(k) 不出问题，
$k$

k 越大越好。

显然，
$k$

k 和
$frac{n}{sqrt{k}}$

k​n​ 成反比，相等时和最小。（反比例函数知识）

所以，
$k=n^{frac{2}{3}}$

k=n32​ 时，时间复杂度达到
$O(n^{frac{2}{3}})$

O(n32​)，是比较优的。

时间复杂度：
$O(Tn^{frac{2}{3}})$

O(Tn32​).

实际得分：
$100pts$

100pts.

博主的代码太丑，不想拿出来了。以后会重构代码发出来的。