P2261 [CQOI2007]余数求和

P2261 [CQOI2007]余数求和

答案为
$$
\begin {aligned}
G(n, k) &= \sum _ {i = 1} ^ n k \mod i \\
&= \sum _ {i = 1} ^ n k - i\left \lfloor \frac k i \right \rfloor \\
&= \sum _ {i = 1} ^ n k - \sum _ {i = 1} ^ n i\left \lfloor \frac k i \right \rfloor \\
&= nk - \sum _ {i = 1} ^ n i\left \lfloor \frac k i \right \rfloor \\
\end {aligned}
$$
直接数论分块即可。需要注意的是，这里 $ 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;
}