「题解」洛谷 P2261 [CQOI2007]余数求和

题目

P2261 [CQOI2007]余数求和

简化题意

求 (G(n,k) = sumlimits_{i = 1}^{n} kmod i)

思路

整除分块。

[egin{aligned} G(n,k) &= sumlimits_{i = 1}^{n} kmod i \ &= sum_{i = 1} ^ {n} k - leftlfloordfrac{k}{i} ight floor imes i \ &= nk - sum_{i = 1} ^ {n}leftlfloordfrac{k}{i} ight floor imes i end{aligned} ]

右边可以整除分块 (O(2sqrt n)) 求出。

Code

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>

int n, k;
long long ans;

int main() {
    std::cin >> n >> k;
    ans = 1ll * n * k;
    for (int i = 1, j = 0; i <= n; i = j + 1) {
        if (k / i == 0) break;
        j = k / (k / i);
        j = j > n ? n : j;
        ans -= 1ll * (k / i) * (1ll * (i + j) * (j - i + 1) / 2);
    }
    std::cout << ans << '
';
    return 0;
}