G题 （打表+二分）

#include <bits/stdc++.h>
using i64 = long long;

void Solve() {
    for (int i = 1; i <= 1000; i ++ ) {
        std::cout << i << ' ' << 1000 % i << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int tt; std::cin >> tt;
    while (tt --) Solve();
    return 0;
}

思路：

可以发现对于每一个 d ，从 x//(d+1)+1 开始，后面形成的是以 d 为公差的递减等差数列。

那么对于小规模数据 (1e6) ，我们直接 sort 解决。

对于大的，我们可以开一个大小为 1001 的数组，存下每个 d 的首相，之前的可以用 1e6 数组中预处理好的。

最后我们二分，取每个大于等于 mid 的数，以取出来的数量是否大于等于 k 为依据，即可算出答案。

代码：

#include <bits/stdc++.h>
using i64 = long long;

constexpr int N = 1E6;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    std::cin >> n >> k;

    int M = std::min(n, N);
    std::vector<int> a(M + 1, n);

    for (int i = 1; i <= M; i ++ ) {
        a[i] %= i;
    }

    std::sort(a.begin() + 1, a.end());

    if (n <= N) {
        i64 ans = 0;
        for (int i = n; i >= n - k + 1; i -- ) {
            ans += a[i];
        }

        std::cout << ans << '\n';

    }else {
        std::vector<int> d(1001);
        for (int i = 1; i < 1001; i ++ ) {
            int st = n / (i + 1) + 1, mod = n % st;
            d[i] = mod;
            if (st <= M) {
                d[i] = std::max(0LL, - i64(M - st + 1) * i + d[i]);
            }
        }

        auto check = [&](int x) {
            int bd = std::lower_bound(a.begin() + 1, a.end(), x) - a.begin();
            i64 res = M + 1 - bd;

            for (int i = 1; i < 1001; i ++ ) {
                if (d[i] >= x) {
                    res += (d[i] - x) / i + 1;
                }
            }

            return res;
        };

        int l = 0, r = n + 1;
        while (l + 1 != r) {
            int mid = l + r >> 1;
            if (check(mid) >= k) l = mid;
            else r = mid;
        }

        i64 ans = 0;
        int bd = std::lower_bound(a.begin() + 1, a.end(), l) - a.begin();
        for (int i = bd; i <= M; i ++ ) {
            ans += a[i];
        }
        
        for (int i = 1; i < 1001; i ++ ) {
            if (d[i] >= l) {
                int num = (d[i] - l) / i + 1;
                ans += (-i64(num - 1) * i + d[i] + d[i]) * num / 2;
            }
        }

        int now = check(l);
        ans -= i64(now - k) * l;

        std::cout << ans << '\n';

    }
    
    return 0;
}