首页
A
2vgfmltt
当前主题：自动模式
查看保存队列
搜索
专栏文章
P3768 简单的数学题
l
lovely_nst
2025/10/21 17:33
个人记录
参与者 1
已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
当前评论
0 条
当前快照
1 份
快照标识符
@minjm1o8
此快照首次捕获于
2025/12/02 03:29
3 个月前
此快照最后确认于
2025/12/02 03:29
3 个月前
查看原文
时光机
更新文章
复制链接
复制快照链接
复制正文 Markdown
P3768 简单的数学题
题意
给定
n
n
n
求：
∑
i
=
1
n
∑
j
=
1
n
i
j
gcd
(
i
,
j
)
\sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j)
i
=
1
∑
n
j
=
1
∑
n
ij
g
cd
(
i
,
j
)
正文
性质：
n
=
∑
d
∣
n
φ
(
d
)
n=\sum_{d|n}\varphi(d)
n
=
d
∣
n
∑
φ
(
d
)
那么：
∑
i
=
1
n
∑
j
=
1
n
i
j
gcd
(
i
,
j
)
=
∑
i
=
1
n
∑
j
=
1
n
i
j
∑
d
∣
gcd
(
i
,
j
)
φ
(
d
)
=
∑
d
=
1
n
φ
(
d
)
∑
i
=
1
n
∑
j
=
1
n
[
gcd
(
i
,
j
)
=
d
]
i
j
=
∑
d
=
1
n
φ
(
d
)
∑
i
=
1
⌊
n
d
⌋
∑
j
=
1
⌊
n
d
⌋
(
i
d
)
(
j
d
)
=
∑
d
=
1
n
φ
(
d
)
d
2
∑
i
=
1
⌊
n
d
⌋
∑
j
=
1
⌊
n
d
⌋
i
j
=
∑
d
=
1
n
φ
(
d
)
d
2
(
∑
i
=
1
⌊
n
d
⌋
i
)
2
\sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j)\\ =\sum_{i=1}^n\sum_{j=1}^nij\sum_{d|\gcd(i,j)}\varphi(d)\\ =\sum_{d=1}^n\varphi(d)\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=d]ij\\ =\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}(id)(jd)\\ =\sum_{d=1}^n\varphi(d)d^2\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}ij\\ =\sum_{d=1}^n\varphi(d)d^2(\sum_{i=1}^{\lfloor\frac nd\rfloor}i)^2\\
i
=
1
∑
n
j
=
1
∑
n
ij
g
cd
(
i
,
j
)
=
i
=
1
∑
n
j
=
1
∑
n
ij
d
∣
g
c
d
(
i
,
j
)
∑
φ
(
d
)
=
d
=
1
∑
n
φ
(
d
)
i
=
1
∑
n
j
=
1
∑
n
[
g
cd
(
i
,
j
)
=
d
]
ij
=
d
=
1
∑
n
φ
(
d
)
i
=
1
∑
⌊
d
n
⌋
j
=
1
∑
⌊
d
n
⌋
(
i
d
)
(
j
d
)
=
d
=
1
∑
n
φ
(
d
)
d
2
i
=
1
∑
⌊
d
n
⌋
j
=
1
∑
⌊
d
n
⌋
ij
=
d
=
1
∑
n
φ
(
d
)
d
2
(
i
=
1
∑
⌊
d
n
⌋
i
)
2
考虑整除分块，之后就是如何求
φ
(
d
)
d
2
\varphi(d)d^2
φ
(
d
)
d
2
的前缀和。考虑杜教筛。
f
∗
g
=
∑
d
∣
x
f
(
d
)
⋅
g
(
x
d
)
g
(
1
)
S
(
n
)
=
∑
i
=
1
n
(
f
∗
g
)
(
i
)
−
∑
d
=
2
n
g
(
d
)
S
(
⌊
n
d
⌋
)
f*g=\sum_{d|x} f(d)\cdot g(\frac xd)\\ g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{d=2}^ng(d)S(\lfloor\frac nd\rfloor)
f
∗
g
=
d
∣
x
∑
f
(
d
)
⋅
g
(
d
x
)
g
(
1
)
S
(
n
)
=
i
=
1
∑
n
(
f
∗
g
)
(
i
)
−
d
=
2
∑
n
g
(
d
)
S
(⌊
d
n
⌋)
那么设
g
(
i
)
=
i
2
g(i)=i^2
g
(
i
)
=
i
2
，此时的
g
g
g
为完全积性函数，同时
(
f
∗
g
)
(
x
)
=
∑
d
∣
x
f
(
d
)
⋅
g
(
x
d
)
=
∑
d
∣
x
φ
(
d
)
d
2
x
2
d
2
=
x
2
∑
d
∣
x
φ
(
d
)
=
x
3
(f*g)(x)\\ =\sum_{d|x}f(d)\cdot g(\frac xd)\\ =\sum_{d|x}\varphi(d)d^2\frac{x^2}{d^2}\\ =x^2\sum_{d|x}\varphi(d)\\ =x^3\\
(
f
∗
g
)
(
x
)
=
d
∣
x
∑
f
(
d
)
⋅
g
(
d
x
)
=
d
∣
x
∑
φ
(
d
)
d
2
d
2
x
2
=
x
2
d
∣
x
∑
φ
(
d
)
=
x
3
S
(
n
)
=
(
∑
i
=
1
n
i
3
)
−
∑
d
=
2
n
d
2
S
(
⌊
n
d
⌋
)
S(n)=(\sum_{i=1}^n i^3)-\sum_{d=2}^nd^2S(\lfloor\frac nd\rfloor)
S
(
n
)
=
(
i
=
1
∑
n
i
3
)
−
d
=
2
∑
n
d
2
S
(⌊
d
n
⌋)
接下来就容易做了。
相关推荐
评论
共 0 条评论，欢迎与作者交流。
最新优先
最早优先
搜索
正在加载评论...