文章目录
- 前言
- 一、例题
- 二、代码及思路
- 1.思路
- 2.代码
前言
杜教筛是一个用来快速求积性函数前缀和的方法，其时间复杂度可达到
O
(
n
2
3
)
O(n^{\frac{2}{3}})
O(n32)，进而可以处理1e9的问题，其原理如下：
设
待
求
和
式
为
S
(
n
)
=
∑
i
=
1
n
f
(
i
)
,
n
=
1
e
9
设待求和式为 S(n)= \sum_{i=1}^{n}f(i), \space n=1e9
设待求和式为S(n)=i=1∑nf(i), n=1e9我们的工作是找一个可在
O
(
1
)
O(1)
O(1)时间内查询的积性函数
g
g
g，那么它与待求和式有如下关系：
∑
i
=
1
n
(
f
∗
g
)
(
i
)
=
∑
i
=
1
n
g
(
i
)
S
(
⌊
n
i
⌋
)
\sum_{i=1}^n(f*g)(i)=\sum_{i=1}^ng(i)S(\lfloor \frac{n}{i} \rfloor)
i=1∑n(f∗g)(i)=i=1∑ng(i)S(⌊in⌋)
简证：
∑
i
=
1
n
(
f
∗
g
)
(
i
)
\sum_{i=1}^n(f*g)(i)
i=1∑n(f∗g)(i)
=
∑
i
=
1
n
∑
d
∣
i
g
(
d
)
f
(
i
d
)
=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d})
=i=1∑nd∣i∑g(d)f(di)
=
∑
i
=
1
n
∑
j
=
1
⌊
n
i
⌋
g
(
i
)
f
(
j
)
=\sum_{i=1}^n\sum_{j=1}^{\lfloor \frac{n}{i} \rfloor}g(i)f(j)
=i=1∑nj=1∑⌊in⌋g(i)f(j)
=
∑
i
=
1
n
g
(
i
)
∑
j
=
1
⌊
n
i
⌋
f
(
j
)
=\sum_{i=1}^ng(i)\sum_{j=1}^{\lfloor \frac{n}{i} \rfloor}f(j)
=i=1∑ng(i)j=1∑⌊in⌋f(j)
=
∑
i
=
1
n
g
(
i
)
S
(
⌊
n
i
⌋
)
=\sum_{i=1}^ng(i)S(\lfloor \frac{n}{i} \rfloor)
=i=1∑ng(i)S(⌊in⌋)进而可以得到一个方便计算的递推式：
g
(
1
)
S
(
n
)
=
∑
i
=
1
n
(
f
∗
g
)
(
i
)
−
∑
i
=
2
n
g
(
i
)
S
(
⌊
n
i
⌋
)
g(1)S(n)=\sum_{i=1}^n(f*g)(i) - \sum_{i=2}^ng(i)S(\lfloor \frac{n}{i} \rfloor)
g(1)S(n)=i=1∑n(f∗g)(i)−i=2∑ng(i)S(⌊in⌋)
我们来分析一下它的时间复杂度，假设我们已预处理过
[
1
,
n
]
[1,\sqrt{n}]
[1,n
]，那么
[
1
,
n
]
[1,\sqrt{n}]
[1,n
]内的前缀和的前缀和的查询为
O
(
t
)
O(\sqrt{t})
O(t
)：
O
(
S
(
n
)
)
=
O
(
1
)
−
O
(
∫
2
n
n
x
d
x
)
=
O
(
n
3
4
)
O(S(n))=O(1)-O(\int_2^{\sqrt{n}}\sqrt{\frac{n}{x}}dx)=O(n^{\frac{3}{4}})
O(S(n))=O(1)−O(∫2n
xn
dx)=O(n43)这个复杂度不错，但我们可以继续改进，预处理
[
1
,
n
2
3
]
[1,n^{\frac{2}{3}}]
[1,n32]的前缀和，则可以得到
O
(
n
2
3
)
O(n^{\frac{2}{3}})
O(n32)的复杂度，证明方法同上
下面给出几个常见的辅助函数：
S
(
i
)
=
∑
i
=
1
n
μ
(
i
)
,
g
(
i
)
=
I
(
i
)
S(i)=\sum_{i=1}^{n}\mu(i), g(i)=I(i)
S(i)=i=1∑nμ(i),g(i)=I(i)
S
(
i
)
=
∑
i
=
1
n
φ
(
i
)
,
g
(
i
)
=
I
(
i
)
S(i)=\sum_{i=1}^{n}\varphi(i), g(i)=I(i)
S(i)=i=1∑nφ(i),g(i)=I(i)
S
(
i
)
=
∑
i
=
1
n
i
2
φ
(
i
)
,
g
(
i
)
=
i
2
S(i)=\sum_{i=1}^{n}i^2\varphi(i), g(i)=i^2
S(i)=i=1∑ni2φ(i),g(i)=i2
一、例题
二、代码及思路
1.思路
直接用 ϕ \phi ϕ 和 μ \mu μ 的板子即可
2.代码
代码如下：
#include
#include
#define int long long
using namespace std;
const int maxn = 5e6;
int miu[maxn], phi[maxn];
int premiu[maxn], prephi[maxn];
int prime[maxn], pn;
bool isp[maxn];
map Smiu;
map Sphi;
void table() {
for (int i = 1; i
关注
打赏
![]()
查看更多评论
