题目
简化题意
求 \(G(n,k) = \sum\limits_{i = 1}^{n} k\mod i\)
思路
整除分块。
\[\begin{aligned} G(n,k) &= \sum\limits_{i = 1}^{n} k\mod i \\ &= \sum_{i = 1} ^ {n} k - \left\lfloor\dfrac{k}{i}\right\rfloor \times i \\ &= nk - \sum_{i = 1} ^ {n}\left\lfloor\dfrac{k}{i}\right\rfloor \times i \end{aligned} \]
右边可以整除分块 \(O(2\sqrt n)\) 求出。
Code
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
int n, k;
long long ans;
int main() {
std::cin >> n >> k;
ans = 1ll * n * k;
for (int i = 1, j = 0; i <= n; i = j + 1) {
if (k / i == 0) break;
j = k / (k / i);
j = j > n ? n : j;
ans -= 1ll * (k / i) * (1ll * (i + j) * (j - i + 1) / 2);
}
std::cout << ans << '\n';
return 0;
}