洛谷 - P2261 余数求和

题面

题目描述

给出正整数 $n$ 和 $k$，请计算：

$$G(n, k) = \sum_{i = 1}^n k \bmod i$$

其中 $k \bmod i$ 表示 $k$ 除以 $i$ 的余数。

输入格式

输入只有一行两个整数，分别表示 $n$ 和 $k$。

输出格式

输出一行一个整数表示答案。

输入输出样例

样例输入 #1

10 5

样例输出 #1

29

样例解释 #1

$G(10, 5) = 0 + 1 + 2 + 1 + 0 + 5 + 5 + 5 + 5 + 5 = 29$。

数据范围与约定

• 对于 $30\%$ 的数据，保证 $n, k \leq 10^3$；
• 对于 $60\%$ 的数据，保证 $n, k \leq 10^6$；
• 对于 $100\%$ 的数据，保证 $1 \leq n, k \leq 10^9$。

思路

$$\begin{aligned} & \sum_{i = 1}^{n} k \bmod i \\ = & \sum_{i = 1}^{n} k - i \lfloor \frac{k}{i} \rfloor \\ = & nk - \sum_{i = 1}^{n} i \times \lfloor \frac{k}{i} \rfloor \\ \end{aligned}$$

然后使用整除分块计算。设 $t = \lfloor \frac{k}{l} \rfloor$，若 $t \ne 0$，则 $r = \lfloor \frac{k}{t} \rfloor$，否则 $r = n$。将 $\it ans$ 减去 $(l + r) / 2 \times t \times (r - l + 1)$（区间内 $i$ 的平均值 × $\lfloor \frac{k}{l} \rfloor$ × 区间长度）。

当 $t = 0$ 时可知余下部分全为 $0$，退出循环即可。

代码

#include <iostream>

using std::cin;
using std::cout;
const char endl = '\n';

long long n, k, ans;

int main() {
    std::ios::sync_with_stdio(false);

    cin >> n >> k;

    ans = n * k;

    for (long long l = 1, r; k / l && l <= n; l = r + 1) {
        r = std::min(k / (k / l), n);
        ans -= (r + l) * (k / l) * (r - l + 1) / 2;
    }

    cout << ans << endl;

    return 0;
}