《P2261 [CQOI2007] 余数求和》

题目描述

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

G(n,k)=i=1∑n​kmodi

其中 kmodi 表示 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≤103。
• 对于 60% 的数据，保证 n,k≤106。
• 对于 100% 的数据，保证 1≤n,k≤109。

2024/2/13 添加一组 hack 数据

代码实现：

#include <iostream> using namespace std; long long sum(int l, int r) { return (l + r) * (r - l + 1ll) >> 1; } int main() { int n, k; cin >> n >> k; long long res = 0; if (k < n) { res = 1ll * (n - k) * k; n = k; } res += 1ll * n * k; for (int i = 1; i <= n; ++i) { int j = min(n, k / (k / i)); res -= sum(i, j) * (k / i); i = j; } cout << res << endl; }