[题解] [CQOI2007] 余数求和

题面

题解

考虑到这个等式\(a\bmod b = a - b * \lfloor\frac{a}{b}\rfloor\)

所以我们可以得到:
\[ \begin{aligned} ans &= \sum_{i = 1}^{n}k \bmod i\\ &= \sum_{i = 1} ^ {n}k - i * \lfloor\frac{k}{i}\rfloor \end{aligned} \]
我们可以证得若\(\lfloor\frac{a}{b}\rfloor\)是相同的, 则对应的b所取得的区间必然是连续的

所以维护一下满足相同的\(\lfloor\frac{a}{b}\rfloor\)的区间的左右端点跳一下就可以了, 注意取值范围

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#define itn int
#define reaD read
using namespace std;

int n, k;
long long ans = 0; 

inline int read()
{
    int x = 0, w = 1; char c = getchar();
    while(c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * w;
}

int main()
{
    n = read(); k = read();
    for(int r, l = 1; l <= n; )
    {
        int t = k / l; r = t ? min(k / t, n) : n;
        ans += 1ll * (r - l + 1) * k - 1ll * (r + l) * (r - l + 1) * t / 2; l = r + 1; 
    }
    printf("%lld\n", ans); 
    return 0;
}