本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-22 15:03:49

整除分块

引入：看题

明显，对于这道题，单纯的 $O(n)$ 枚举会爆时间，这时候我们就要引入 整除分块 的芝士了。

举例及分块有关知识

以 $16$ 为例，$n=16$ 时,枚举 $\lfloor \frac{n}{i} \rfloor$ 的情况。

这时候我们会发现，$\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;
}

一道蓝题就这样被水过了......