Luogu2261 [CQOI2007]余数求和

link

Sol

整除分块入门题

现在让你求得是

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

模运算这种东西就是带余除法，然后你发现余数你也很不好算。就考虑把模运算改成带余除法的形式

我们知道: x \div i = \lfloor \frac{x}{i} \rfloor + x - (i \times \lfloor \frac{x}{i} \rfloor)

所以现在要求的东西就是

\sum_{i=1}^{n} x - (i \times \lfloor \frac{x}{i} \rfloor)

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

n 的范围是10^9，所以后面那一块东西就用整除分块做掉

比如说你打表发现 n=10 的时候，得到的\lfloor \frac{x}{i} \rfloor分别是 10 5 3 2 2 1 1 1 1 1

所以\lfloor \frac{x}{i} \rfloor是有规律的，并且结论是：假如一个块的起始位置是l，那么终止位置r= \lfloor \frac{x}{\lfloor \frac{x}{i} \rfloor} \rfloor

现在前面还乘了一个 i ,观察到 \sum_{i=1}^{n} i 这是一个等差数列。所以可以直接等差数列求一段的和

事实上，只要是积性函数，都会满足这个性质

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 1e5 + 5;

int n, k;

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

signed main()
{
    n = read(), k = read();
    int ans = n * k;
    for (int l = 1, r; l <= n; l = r + 1) {
        if (k / l != 0) r = std::min(k / (k / l), n);
        else r = n;
        ans -= (k / l) * (r - l + 1) * (l + r) / 2;
        // printf("l:%d r:%d ans:%d\n", l, r, ans);
    }
    printf("%lld\n", ans);
    return 0;
}