一、问题引入
试快速计算下式：
Σ
i
=
1
n
f
(
i
)
g
(
?
n
i
?
)
\Sigma_{i=1}^{n}f(i)g(\lfloor \frac{n}{i} \rfloor)
Σi=1n?f(i)g(?in??)
其中，
f
(
x
)
f(x)
f(x) 的前缀和已预处理（或可预处理），
g
(
x
)
g(x)
g(x) 可以
O
(
1
)
O(1)
O(1) 计算。
二、分析
首先，我们可以发现，在
i
i
i 从
1
1
1 到
n
n
n 单调递增的过程中，
?
n
i
?
\lfloor \frac{n}{i} \rfloor
?in?? 的值从
n
n
n 到
1
1
1 单调递减，但变化次数远远少于
n
n
n 次，因此可以考虑将
?
n
i
?
\lfloor \frac{n}{i} \rfloor
?in?? 相同的情况合并，统一计算。更换枚举方式，简化为下式：
Σ
i
=
1
n
f
(
i
)
g
(
?
n
i
?
)
=
Σ
j
∈
S
(
s
u
m
f
(
r
j
)
?
s
u
m
f
(
l
j
)
)
g
(
j
)
,
S
=
{
?
n
i
?
∣
i
∈
N
+
,
i
?
n
}
\Sigma_{i = 1}^{n}f(i)g(\lfloor \frac{n}{i}\rfloor) = \Sigma_{j \in S} (sumf(r_{j}) - sumf(l_{j}))g(j), S = \lbrace\lfloor\frac{n}{i}\rfloor\mid i \in \mathbb{N}_{+}, i \leqslant n \rbrace
Σi=1n?f(i)g(?in??)=Σj∈S?(sumf(rj?)?sumf(lj?))g(j),S={?in??∣i∈N+?,i?n}
经过简化，从
1
1
1 到
n
n
n 的枚举范围降低到了枚举
S
S
S 集合。那么
S
S
S 集合究竟有多大呢？有引理如下。
Lemma.
?
n
∈
N
+
,
∣
{
?
n
i
?
∣
i
∈
N
+
,
i
?
n
}
∣
?
2
n
，
\forall n \in \mathbb{N}_{+}, \left|\left\{\lfloor\frac{n}{i}\rfloor \mid i \in \mathbb{N}_{+},i\leqslant n\right\}\right| \leqslant 2\sqrt{n}，
?n∈N+?,∣∣?{?in??∣i∈N+?,i?n}∣∣??2n
?，
∣
S
∣
\left|S\right|
∣S∣ 表示集合
S
S
S 的大小。
简略证明如下：
当
i
i
i 小于
n
\sqrt{n}
n
? 时，
?
n
i
?
\lfloor\frac{n}{i}\rfloor
?in?? 至多有
n
\sqrt{n}
n
? 种取值。
当
i
i
i 大于
n
\sqrt{n}
n
? 时，
1
?
?
n
i
?
?
n
1\leqslant \lfloor\frac{n}{i}\rfloor \leqslant n
1??in???n ，也至多有
n
\sqrt{n}
n
? 种取值。
因此，
?
n
i
?
\lfloor\frac{n}{i}\rfloor
?in?? 总共至多
2
n
2\sqrt{n}
2n
? 种取值。
最后，分析一下更换枚举后的复杂度。枚举至多
2
n
2\sqrt{n}
2n
? 次，单次计算区间和和
g
(
x
)
g(x)
g(x) 函数值均可以在
O
(
1
)
O(1)
O(1) 的时间复杂度内解决，因此总复杂度为
O
(
n
)
O(\sqrt{n})
O(n
?)。
三、例题和代码
（1）UVA11526
题目大意：
T
T
T 组数据，每组给定一个
n
n
n ，求下式的值。
Σ
i
=
1
n
?
n
i
?
\Sigma_{i=1}^{n}\lfloor\frac{n}{i}\rfloor
Σi=1n??in??
解：数论分块板子题。其中
f
(
x
)
≡
1
,
g
(
x
)
=
x
f(x) \equiv 1,g(x) = x
f(x)≡1,g(x)=x。代码如下。
#include<bits/stdc++.h>
using namespace std;
int T, n;
int sumf(int x){
return x;
}
int g(int x){
return x;
}
int main(){
scanf("%d", &T);
while (T --){
scanf("%d", &n);
long long l = 1, r, ans = 0;
while (l <= n){
r = n / (n / l);
ans += (sumf(r) - sumf(l - 1)) * g(n / l);
l = r + 1;
}
printf("%lld\n", ans);
}
return 0;
}
(2) P2261
题目大意：给定
n
n
n 和
k
k
k ，求下式的值。
G
(
n
,
k
)
=
Σ
i
=
1
n
k
%
i
G(n,k) = \Sigma_{i = 1}^{n}{k}\%{i}
G(n,k)=Σi=1n?k%i
其中
%
\%
% 为取余运算。
解：转化。
G
(
n
,
k
)
=
Σ
i
=
1
n
k
%
i
=
Σ
i
=
1
n
(
k
?
i
?
k
i
?
)
=
Σ
i
=
1
n
k
?
Σ
i
=
1
n
i
?
k
i
?
G(n,k) = \Sigma_{i = 1}^{n}{k}\%{i} = \Sigma_{i = 1}^{n}(k - i\lfloor\frac{k}{i}\rfloor) = \Sigma_{i = 1}^{n}k - \Sigma_{i = 1}^{n}i\lfloor\frac{k}{i}\rfloor
G(n,k)=Σi=1n?k%i=Σi=1n?(k?i?ik??)=Σi=1n?k?Σi=1n?i?ik??
与数论分块的模板式子很相似，可以确定两个函数分别为
f
(
x
)
=
x
,
g
(
x
)
=
x
f(x) = x, g(x) = x
f(x)=x,g(x)=x 。不过上界不同，分类讨论即可。
对于
k
?
n
k\leqslant n
k?n的情况，由于
i
?
k
i\geqslant k
i?k 时
?
k
i
?
=
0
\lfloor\frac{k}{i}\rfloor = 0
?ik??=0，没有影响。
对于
k
>
n
k \gt n
k>n 的情况，需要判断区间的右端点
r
r
r 是否超过
n
n
n ，如果超过，则需要修改。代码如下。
#include<bits/stdc++.h>
using namespace std;
int n, k;
long long sumf(int x){
return 1ll * x * (x + 1) / 2;
}
long long g(int x){
return x;
}
int main(){
scanf("%d%d", &n, &k);
if (k <= n){
long long l = 1, r, ans = 0;
while (l <= k){
r = k / (k / l);
ans += (sumf(r) - sumf(l - 1)) * g(k / l);
l = r + 1;
}
printf("%lld\n", 1ll * n * k - ans);
}
else {
long long l = 1, r, ans = 0;
while (l <= n){
r = k / (k / l);
if (r > n) r = n;
ans += (sumf(r) - sumf(l - 1)) * g(k / l);
l = r + 1;
}
printf("%lld\n", 1ll * n * k - ans);
}
return 0;
}
|