题目信息
题目来源：CCF 重庆省选 2007；
在线评测地址：Luogu#2261；
运行限制：时间不超过 (1.00 extrm{s})，空间不超过 (128 extrm{MiB})。
题目描述
给出正整数 (n) 和 (k)，请计算
[G(n,k) = sumlimits_{i=1}^n kmod i
]
其中 (kmod i) 表示 (k) 除以 (i) 的余数。
输入格式
输入只有一行两个整数，分别表示 (n) 和 (k)。
输出格式
输出一行一个整数表示答案。
数据规模与约定
- 对于 (30\%) 的数据，保证 (n,kle 10^3)；
- 对于 (60\%) 的数据，保证 (n,kle 10^6)；
- 对于 (100\%) 的数据，保证 (1le n,kle 10^9)。
分析
这道题又是一个十分经典的数论题。
(60 exttt{ pts})
直接暴力乱搞即可。
(100 exttt{ pts})
说实话这道题数据有那么亿点水。
我们来推个式子：
[egin{aligned}
G(n,k)= & sumlimits_{i=1}^n kmod{i}\
=& sumlimits_{i=1}^nleft(k-leftlfloordfrac{k}{i}
ight
floor
ight)\
=&\, nk-sumlimits_{i=1}^nleftlfloordfrac{k}{i}
ight
floor
end{aligned}
]
后面那一半是经典的整数分块，直接 (mathcal{O}(sqrt{k})) 就可以解决。所以这道题的数据范围应该开到 1e14 然后再取模的吧
怎么证明整数分块的复杂度？
对于 (leftlfloordfrac{k}{i} ight floorle sqrt{k}) 的，值必然最多只有 (sqrt{k}) 个，所以这一部分是 (mathcal{O}(sqrt{k})) 的。
对于 (leftlfloordfrac{k}{i} ight floor > sqrt{k}) 的，则 (dfrac{k}{i}>sqrt{k})，可以得到 (i<dfrac{k}{sqrt{k}}=sqrt{k})，即这样的数的个数最多只有 (sqrt{k}) 个，一样是 (mathcal{O}(sqrt{k})) 的。
所以整体的复杂度是 (mathcal{O}(sqrt{k}))
注意事项
因为特殊的原因，这道题请将所有变量开 long long，否则会出大问题。
同时，别忘了整数分块中对 (r) 变量上界的把握。
Code
#include <cstdio>
using namespace std;
typedef long long ll;
ll my_min(ll a, ll b) { return (a < b)? a:b; } // 最小值函数
int main()
{
ll l, r, n, k, ans;
scanf("%lld%lld", &n, &k); // 输入
ans = 1ll * n * k;
for (l = 1; l <= n; l = r + 1) // 分块
{
if (k / l)
r = my_min(k / (k / l), n); // 别忘了取最小值，否则只有 50 分
else
r = n;
ans -= 1ll * (k / l) * (l + r) * (r - l + 1) / 2; // 统计进去
}
printf("%lld
", ans); // 输出
return 0; // 然后就 AC 了、
}