\sum_{i = 1}^n k \bmod i
## Analysis
考虑处理取模。一个经典套路是 $k \bmod i = k - i\left\lfloor\frac k i \right\rfloor$（回忆 exgcd 的证明也是一样的式子）。于是：
$$\begin{aligned}\sum_{i = 1}^n k \bmod i &= \sum_{i = 1}^n (k - i \left\lfloor\frac k i \right\rfloor) \\ &= \sum_{i = 1}^n k - \sum_{i = 1}^n i\left\lfloor\frac k i \right\rfloor\end{aligned}$$
减号左边就是 $nk$，可以 $O(1)$ 算，右边长了一副可以整除分块的脸。
> 整除分块：
> 对已知部分和（前缀和）的函数 $f(x)$，计算 $\sum_{i = 1}^n f(i) \left\lfloor\frac n i \right\rfloor$ 的方法：
>
> 易证 $\left\lfloor\frac n i \right\rfloor$ 只有 $O(\sqrt n)$ 种取值，且 $i$ 增大时，该式取值不减。可以证明，对于一个确定的 $x$，满足 $\left\lfloor\frac n j \right\rfloor = x$ 的最大的 $j$ 为 $\left\lfloor\frac n x \right\rfloor$。考虑把 $\left\lfloor\frac n i \right\rfloor$ 值相同的 $i$ 看作一块，那么第一块的左端点为 $i = 1$；假如当前块的左端点是 $i = l$，则右端点为 $i = r = \left\lfloor\frac {n}{\left\lfloor\frac n i \right\rfloor} \right\rfloor$，下一块的左端点为 $r + 1$。
>
> 枚举这 $O(\sqrt n)$ 个块。对于一个块 $[l, r]$，对所求式子的贡献就是 $\left\lfloor\frac n l \right\rfloor \times \sum_{i = l}^r f(i)$。如果可以 $O(T)$ 求函数 $f(x)$ 的部分和，就可以用 $O(T \sqrt n)$ 的复杂度算出所求。
>
> 更细致的介绍见 [OI wiki](https://oi-wiki.org/math/number-theory/sqrt-decomposition/)。
考虑式子 $\sum_{i = 1}^n i\left\lfloor\frac k i \right\rfloor$，对应到整除分块有 $f(x) = x$，但是和整除分块长得不一样的地方在于，求和上限是 $n$ 而不是 $k$。这样是无法保证复杂度的。
考虑把原式拆成 $i \leq k$ 和 $i > k$ 两部分。易见，当 $i > k$ 时，$k \bmod i = k$。而 $i \leq k$ 情况的求和上界至多是 $k$。
于是
$$\begin{aligned}\sum_{i = 1}^n k \bmod i &= \max(0, n - k) \times k + \sum_{i = 1}^{\min(n, k)} (k - i \left\lfloor\frac k i \right\rfloor) \\ &= \max(0, n - k) \times k + \min(n, k) \times k - \sum_{i = 1}^{\min (n,k)}i\left\lfloor\frac k i \right\rfloor\end{aligned}$$
等号右侧前两项都可以 $O(1)$ 计算，第三项相当于对 $\sum_{i = 1}^k i \left\lfloor\frac k i \right\rfloor$ 做整除分块，但是把块右端点最大值限制为 $\min(n, k) \leq k$，复杂度显然是 $O(\sqrt n)$。
## Code
```cpp
#include <iostream>
int main() {
int n, k;
std::cin >> n >> k;
auto sum = [](int l, int r) -> long long {
return (l + r) * (r - l + 1ll) >> 1;
};
long long ans = 0;
if (k < n) {
ans = 1ll * (n - k) * k;
n = k;
}
ans += 1ll * n * k;
for (int l = 1; l <= n; ++l) {
int r = std::min(n, k / (k / l));
ans -= sum(l, r) * (k / l);
l = r;
}
std::cout << ans << std::endl;
}
```