【luogu P4213】【模板】杜教筛(Sum)(数学)(整除分块)
【模板】杜教筛(Sum)
题目链接:luogu P4213
题目大意
要你求 φ 函数的前缀和和 μ 函数的前缀和。
(分别是欧拉函数和莫比乌斯函数)
思路
前置知识(们)
积性函数:对于两个互质的数
x
,
y
x,y
x,y,
f
(
x
y
)
=
f
(
x
)
f
(
y
)
f(xy)=f(x)f(y)
f(xy)=f(x)f(y),那
f
f
f 就是积性函数。
完全积性函数:对于任意两个整数
x
,
y
x,y
x,y,
f
(
x
y
)
=
f
(
x
)
f
(
y
)
f(xy)=f(x)f(y)
f(xy)=f(x)f(y),那
f
f
f 就是完全积性函数。
一些积性函数:
φ
,
μ
,
d
,
σ
\varphi,\mu,d,\sigma
φ,μ,d,σ
(分别是欧拉函数,莫比乌斯函数,约数个数,约数个数和)
一些完全积性函数:
ϵ
,
I
,
i
d
\epsilon,I,id
ϵ,I,id
ϵ
(
n
)
=
[
n
=
1
]
,
I
(
n
)
=
1
,
i
d
(
n
)
=
n
\epsilon(n)=[n=1],I(n)=1,id(n)=n
ϵ(n)=[n=1],I(n)=1,id(n)=n
狄利克雷卷积:
有两个函数
f
,
g
f,g
f,g,它们的狄利克雷卷积:
(
f
∗
g
)
(
n
)
=
∑
d
∣
n
f
(
d
)
g
(
n
d
)
(f*g)(n)=\sum\limits_{d|n}f(d)g(\dfrac{n}{d})
(f∗g)(n)=d∣n∑f(d)g(dn)
不难看出,它满足交换律和结合律。
然后单位元就是
ϵ
\epsilon
ϵ。
然后又一些性质:(根据定义简单推一推都不难看出)
μ
∗
I
=
ϵ
\mu*I=\epsilon
μ∗I=ϵ
φ
∗
I
=
i
d
\varphi*I=id
φ∗I=id
μ
∗
i
d
=
φ
\mu*id=\varphi
μ∗id=φ
莫反:
如果
g
(
n
)
=
∑
d
∣
n
f
(
d
)
g(n)=\sum\limits_{d|n}f(d)
g(n)=d∣n∑f(d)
那么
f
(
n
)
=
∑
d
∣
n
μ
(
d
)
g
(
n
d
)
f(n)=\sum\limits_{d|n}\mu(d)g(\dfrac{n}{d})
f(n)=d∣n∑μ(d)g(dn)
这个地方的证明其实可以用 μ ∗ I = ϵ \mu*I=\epsilon μ∗I=ϵ
给出条件相当于 g = f ∗ I g=f*I g=f∗I
然后 g ∗ μ = f ∗ I ∗ μ = f ∗ ϵ = f g*\mu=f*I*\mu=f*\epsilon=f g∗μ=f∗I∗μ=f∗ϵ=f。
杜教筛
杜教筛就是用来求积性函数的前缀和 s u m ( n ) = ∑ i = 1 n f ( i ) sum(n)=\sum\limits_{i=1}^nf(i) sum(n)=i=1∑nf(i)
考虑再找一个积性函数
g
g
g,求他们的狄利克雷卷积:
∑
i
=
1
n
(
f
∗
g
)
(
i
)
\sum\limits_{i=1}^n(f*g)(i)
i=1∑n(f∗g)(i)
=
∑
i
=
1
n
∑
d
∣
n
f
(
d
)
g
(
i
d
)
=\sum\limits_{i=1}^n\sum\limits_{d|n}f(d)g(\dfrac{i}{d})
=i=1∑nd∣n∑f(d)g(di)
=
∑
d
=
1
n
g
(
d
)
∑
i
=
1
⌊
n
d
⌋
f
(
i
)
=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}f(i)
=d=1∑ng(d)i=1∑⌊dn⌋f(i)
=
∑
d
=
1
n
g
(
d
)
s
u
m
(
⌊
n
d
⌋
)
=\sum\limits_{d=1}^ng(d)sum(\left\lfloor\dfrac{n}{d}\right\rfloor)
=d=1∑ng(d)sum(⌊dn⌋)
然后考虑
g
(
1
)
s
u
m
(
n
)
g(1)sum(n)
g(1)sum(n),根据前缀和:
=
∑
i
=
1
n
g
(
i
)
s
u
m
(
⌊
n
i
⌋
)
−
∑
i
=
2
n
g
(
i
)
s
u
m
(
⌊
n
i
⌋
)
=\sum\limits_{i=1}^ng(i)sum(\left\lfloor\dfrac{n}{i}\right\rfloor)-\sum\limits_{i=2}^ng(i)sum(\left\lfloor\dfrac{n}{i}\right\rfloor)
=i=1∑ng(i)sum(⌊in⌋)−i=2∑ng(i)sum(⌊in⌋)
=
∑
i
=
1
n
(
f
∗
g
)
(
i
)
−
∑
i
=
2
n
g
(
i
)
s
u
m
(
⌊
n
i
⌋
)
=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{i=2}^ng(i)sum(\left\lfloor\dfrac{n}{i}\right\rfloor)
=i=1∑n(f∗g)(i)−i=2∑ng(i)sum(⌊in⌋)
那这个式子就是我们杜教筛要用的式子了。
有什么用呢,大概就是对于每个你要求的 f f f,如果你能找到一个合适的 g g g,它和 f f f 乘起来很好算而且 g g g 也好搞的话就可以拿来用。
就这题的例子,
μ
∗
I
=
ϵ
\mu*I=\epsilon
μ∗I=ϵ,所以左边部分就
ϵ
\epsilon
ϵ 的前缀和是
1
1
1,然后右边你可以用整除分块
O
(
n
)
O(\sqrt{n})
O(n) 搞。
然后
φ
∗
I
=
i
d
\varphi*I=id
φ∗I=id,然后左边部分就
i
d
id
id 的前缀和是
(
1
+
n
)
n
2
\dfrac{(1+n)n}{2}
2(1+n)n,右边也是整除分块过去。
(然后这两个右边
g
(
i
)
g(i)
g(i) 因为是整除分块也可以同前缀和求出,因为是
I
I
I 所以就是
r
−
l
+
1
r-l+1
r−l+1,即块的大小)
然后你可以预处理出
n
2
3
n^{\frac{2}{3}}
n32 以内的结果,复杂度就可以压到
O
(
n
2
3
)
O(n^{\frac{2}{3}})
O(n32)。
(然后你还可以用
m
a
p
map
map 弄个小小的记忆化)
代码
#include<map>
#include<cstdio>
#define ll long long
using namespace std;
//const int Maxn = 1664511;
const int Maxn = 2000000;
int T, np[Maxn + 1], prime[Maxn + 1];
int miu[Maxn + 1], x;
ll phi[Maxn + 1];
map <int, int> ans_miu;
map <int, ll> ans_phi;
void init() {//预处理 n^{2/3} 的部分
miu[1] = phi[1] = 1;
for (int i = 2; i <= Maxn; i++) {
if (!np[i]) {
prime[++prime[0]] = i;
miu[i] = -1;
phi[i] = i - 1;
}
for (int j = 1; j <= prime[0] && i * prime[j] <= Maxn; j++) {
if (i % prime[j]) miu[i * prime[j]] = -miu[i], phi[i * prime[j]] = phi[i] * (prime[j] - 1), np[i * prime[j]] = prime[j];
else {
miu[i * prime[j]] = 0, phi[i * prime[j]] = phi[i] * prime[j], np[i * prime[j]] = prime[j];
break;
}
}
}
for (int i = 1; i <= Maxn; i++)//前缀和起来
miu[i] += miu[i - 1], phi[i] += phi[i - 1];
}
ll get_phi(int x) {
if (x <= Maxn) return phi[x];
if (ans_phi[x]) return ans_phi[x];
ll re = 1ll * (1ll + x) * x / 2;//id 函数的前缀和
for (ll l = 2, r; l <= x; l = r + 1) {
r = x / (x / l);
re -= 1ll * (r - l + 1) * get_phi(x / l);
}
return ans_phi[x] = re;
}
int get_miu(int x) {
if (x <= Maxn) return miu[x];
if (ans_miu[x]) return ans_miu[x];
ll re = 1;//ϵ 函数的前缀和
for (ll l = 2, r; l <= x; l = r + 1) {
r = x / (x / l);
re -= 1ll * (r - l + 1) * get_miu(x / l);
}
return ans_miu[x] = re;
}
int main() {
init();
scanf("%d", &T);
while (T--) {
scanf("%d", &x);
printf("%llu %d\n", get_phi(x), get_miu(x));
}
return 0;
}
相关文章
- MVC的验证(模型注解和非侵入式脚本的结合使用) .Net中初探Redis .net通过代码发送邮件 Log4net (Log for .net) 使用GDI技术创建ASP.NET验证码 Razor模板引擎 (RazorEngine) .Net程序员应该掌握的正则表达式
- Flask框架中Jinja2模板控制语句
- [UWP 自定义控件]了解模板化控件(9):UI指南
- Deepgreen(Greenplum) 模板数据库template0和template1 探讨
- PHP设计模式之模板方法模式定义与用法详解
- [模板题]n-皇后问题
- 洛谷 P3387 【模板】缩点
- 圣诞节熬夜整理一套SSM模板,让你可以快速搭建环境
- IntelliJ Idea13无法创建maven模板
- C++实操 - 模板
- 接口测试用例模板
- Java idea 创建SqlMapConfig.xml,需要新增一个mybatis-cfg.xml模板