P2261 [CQOI2007]余数求和

P2261 [CQOI2007]余数求和

答案为
$$\begin{array}{rl}G(n,k)& =\sum _{i=1}^{n}k\mathrm{mod}i\\ & =\sum _{i=1}^{n}k-i\lfloor \frac{k}{i}\rfloor \\ & =\sum _{i=1}^{n}k-\sum _{i=1}^{n}i\lfloor \frac{k}{i}\rfloor \\ & =nk-\sum _{i=1}^{n}i\lfloor \frac{k}{i}\rfloor \end{array}$$
直接数论分块即可。需要注意的是，这里 $n\ne k$ ，所以 r = min(n, k / (k / l)); 而不是 r = k / (k / l); 。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n, k;
int main()
{
    scanf("%lld%lld", &n, &k);
    LL res = n * k;
    for (int l = 1, r; l <= min(n, k); l = r + 1)
    {
        r = min(n, k / (k / l));
        res -= (k / l) * (l + r) * (r - l + 1) / 2;
    }
    printf("%lld", res);
    return 0;
}