本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-22 15:03:49
整除分块
引入：看题
明显，对于这道题，单纯的 $O(n)$ 枚举会爆时间，这时候我们就要引入 整除分块 的芝士了。
举例及分块有关知识
以 $16$ 为例，$n=16$ 时,枚举 $\lfloor \frac{n}{i} \rfloor$ 的情况。
| $i$ | $\lfloor \frac{n}{i} \rfloor$ |
|---|---|
| ${\color{red}1}$ | ${\color{red}16}$ |
| ${2}$ | ${8}$ |
| ${\color{orange}3}$ | ${\color{orange}5}$ |
| $\color{purple}4$ | $\color{purple}4$ |
| ${\color{yellow}5}$ | ${\color{yellow}3}$ |
| ${\color{green}6}$ | ${\color{green}2}$ |
| ${\color{green}7}$ | ${\color{green}2}$ |
| ${\color{green}8}$ | ${\color{green}2}$ |
| $\textcolor{blue}{9-16}$ | ${\color{blue}1}$ |
这时候我们会发现，$\lfloor \frac{n}{i} \rfloor$ 被分成了一个个块，在同一个块中 $\lfloor \frac{n}{i} \rfloor$ 的值不变，如 $data (块的值) = 2$ 时，$l = 6,r = 8$；$data=1$ 时，$l = 9,r = 16$。
块的个数
当 $i \le \sqrt{n}$ 时，
此时最多分块 $\sqrt{n}$ 个（一个块最少要对应一个 $i$，明显块最小，即块的长度为 $1$ 时，块最多）。
当 $i > \sqrt{n}$ 时，
此时最多的分块也是 $\sqrt n$ 个（$i \times \lfloor \frac n i \rfloor$ 近似等于 $n$，所以 $\lfloor \frac n i \rfloor$ 最多会有 $\sqrt n$ 个）。
综上，$size(\text{分块}) \le 2\sqrt n$。
块的范围
(设第 $i$ 个块的左端点为 $l_i$，右端点为 $r_i$)
易得 $l_1 = 1,l_i = r_{i-1} + 1$，即当前分块的左端点是上一个分块的右端点的下一个。
那怎么求 $r_i$ 呢？
我们可以设 $\lfloor \frac n i \rfloor$ 为 $data$，则在同一个分块中 $data$ 的值不变（由定义得）。
$r_i$ 代表的是满足 $data$ 不变的最大值，我们可以倒过来推，$r_i \times data \le n$（当且仅当 $data\mid n$ 时等号成立），而我们要求最大，所以就有
$$r_i = \lfloor\frac n{data}\rfloor = \lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor}\rfloor$$
如此我们便可以知道块的右端点位置了。
回到题目
朴素做法：
这个应该很容易想到，时间复杂度为 $O(n)$ 的做法：直接照着题目需求枚举 $k \bmod i$，累加即可。但很明显这样会爆，所以看下面的做法：
转化、分解一下需要求的等式：
下面的非常非常重要！！！ $$ \sum_{i=1}^n k \bmod i $$ $$ = \sum_{i=1}^n k - \lfloor \frac k i \rfloor \times i $$ $$ = n\cdot k - \sum_{i=1}^n \lfloor \frac k i \rfloor \times i $$ 我们知道，当 $i > k$ 时，$\lfloor \frac k i \rfloor$ 一定为零，所以: $$ \text{原式} = n\cdot k - \sum_{i=1}^{\min (k,n)} \lfloor \frac k i \rfloor \times i $$
做法（应用分块）
学过整除分块后（当然刚刚学了），我们会知道在同一个块中，$\lfloor \frac k i \rfloor$ 的值不变，而一个除法分块的左右端点可求（在此我用 l,r 表示），所以在同一个分块中，$\sum_{i=1}^n \lfloor \frac k i \rfloor \times i$ 就变成了：
$$
\sum_{i= \text{当前分块的l}}^{\text{当前分块的r}} \lfloor \frac k i \rfloor \times i
$$
$$
= \lfloor \frac k i \rfloor \times l +\lfloor \frac k i \rfloor \times (l+1) +...+\lfloor \frac k i \rfloor \times r
$$
乘法分配律得
$$
\lfloor \frac k i \rfloor \times [l+(l+1)+(l+2)+...+r]
$$
等差数列求和公式：（首项加末项）乘项数除以二，得到：
$$
\lfloor\frac k i\rfloor \times \frac{(l+r) \times (r-l+1)}2
$$
很明显这是一个时间复杂度为 $O(1)$ 的公式，对于每一个分块我们都可以进行一次这样的操作，而分块的个数是 $\sqrt k$ 量级的，所以时间复杂度就由开始的 $O(n)$ 变成了 $O(\sqrt n)$ 了。
下面给出代码：
#include<bits\/stdc++.h>
using namespace std;
#define int long long
#define F(i,j,n) for(int i = j;i <= n;i ++)
const int N = 1e6 + 50,M = 1e3 + 50;
int n,k;
int l,r,ans;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> k;
ans = n * k;\/\/初值
for(int l = 1;l <= n;l = r + 1){
if(l > k) r = n;
\/\/l > k 时,k\/l为0,此时k\/0,会RE;
else r = min(k \/ (k\/l),n);
\/\/r最大到n
ans -= (k\/l) * (l + r) * (r-l+1)\/2;
\/\/等差数列求和
}
cout << ans;
return 0;
}
一道蓝题就这样被水过了......
鲁ICP备2025150228号