题解 P2261 【[CQOI2007]余数求和】

· · 题解

前置知识：整除分块

整除分块就是:

\sum_{i=1}^{n}\lfloor \frac{k}{i} \rfloor

这道题让我们求

\sum_{i=1}^{n}k\ mod\ i

这个式子可以写成这样

\sum_{i=1}^{n}k-\lfloor\frac{k}{i}\rfloor\times i n\times k-\sum_{i=1}^{n}\lfloor\frac{k}{i}\rfloor\times i

我们知道对于每一个整除分块

\sum_{i=l}^{r}\lfloor \frac{k}{i} \rfloor

中的值都是一样的，所以我们可以设\ T=\lfloor \frac{k}{i} \rfloor

这个式子就变成了

\sum_{i=l}^{r}T\times i \sum_{i=l}^{r}T\times\sum_{i=l}^{r}i

至此，我们可以在\Omega(\sqrt{N})的时间内用整除分块解决问题

#include <cstdio>
#define int long long

template < typename T>
inline T getmin(T x, T y) { return x > y ? y : x; }

signed main() {
    long long n, k, ans = 0;
    scanf("%lld %lld", &n, &k);
    for (long long l = 1, r = 0, t; l <= n; l = r + 1) r = (t = k / l) ? getmin(k / t, n) : n, ans -= t * (r - l + 1) * (l + r) >> 1;
    printf("%lld\n", ans = ans + n * k);
}