那怎么求 r_i 呢？
我们可以设 \lfloor \frac n i \rfloor 为 data，则在同一个分块中 data 的值不变（由定义得）。
$$r_i = \lfloor\frac n{data}\rfloor = \lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor}\rfloor$$
如此我们便可以知道块的右端点位置了。
## 回到[题目](https://www.luogu.com.cn/problem/P2261)
### 朴素做法：
这个应该很容易想到，时间复杂度为 $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)$ 了。
### 下面给出代码：
```cpp
#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;
}
```
~~一道蓝题就这样被水过了......~~