个人题解G

感觉很长时间没写过题解了，不过我这种彩笔也就写写签到了

这场总体感觉偏难，而且区分度有点低？四道签到（A，M，F，L）两道中档（C，E），剩下的感觉都very hard（这是能说的吗）

关于G：

关键字：二分，整除分块

第一眼看过去就知道肯定是整除分块，对于每个块，我们可以将其看作一段长为等差数列。

我们定义一个分块为Block：

struct Block { int a, b, q; }; // [a,b]除数区间，对应商为q

其中[a,b]为除数区间，对于任意i属于[a,b]，有；

此时我们知道，对于任意i属于[a,b]，n%i的值构成一个等差数列，此时区间内的最大余数为n mod a，即n-q*a。

不妨暴力的考虑：将所有的分块放入一个优先队列中，按照最大余数的大小进行排序，每次从区间中取出一个最大余数，更新区间，再将其放回队列中，直到取满k个元素。

显然对于k=1e9的数据规模这是必定超时的。

如何优化呢？

这里有一个很巧妙的方法：我们可以二分计算出一个阈值T，T表示大于等于T的余数至少有k个。

那么问题就迎刃而解了：我们只需要遍历所有区间，每个区间取出所有大于等于T的余数，此时元素数量可能多于k个，显然多出来的元素大小一定是T，那么只需要将其减去即可。

代码：

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
#define ll long long

struct Block { int a, b, q; }; // [a,b]除数区间，对应商为q
vector<Block> blocks;

void build(int n) {
    blocks.clear();
    for(int q=1, r; q<=n; q=r+1) {
        r = n/(n/q); // 计算当前商对应的除数区间右边界
        blocks.push_back({q, r, n/q}); // 存储除数区间[q,r]和商
        if(r == n) break; // 终止条件
    }
}

ll count(int T, int n) {
    ll cnt = 0;
    for(auto &blk : blocks) {
        int q_val = blk.q;
        int max_i = (n - T)/q_val; // 最大满足条件的除数
        int low = max(blk.a, 1);    // 除数区间下限
        int high = min(blk.b, max_i);
        if(high >= low) cnt += high - low + 1;
    }
    return cnt;
}

ll sum(int T, int n) {
    ll s = 0;
    for(auto &blk : blocks) {
        int q_val = blk.q;
        int max_i = (n - T)/q_val;
        int low = max(blk.a, 1);
        int high = min(blk.b, max_i);
        
        if(high >= low) {
            int cnt = high - low + 1;
            int first = n - q_val*low;  // 首项余数
            int last = n - q_val*high;  // 末项余数
            s += (ll)(first + last)*cnt/2;
        }
    }
    return s;
}

void solve() {
    int n, k;
    cin >> n >> k;
    
    build(n); // 构建分块
    
    // 二分求临界值T
    int l=0, r=n, T=0;
    while(l <= r) {
        int mid = (l+r)/2;
        count(mid, n) >= k ? (T=mid,l=mid+1) : (r=mid-1);
    }
    
    ll total = sum(T, n);
    ll cnt = count(T, n);
    cout << total - (cnt - k)*T << endl;
}

int main() {
    solve();
    return 0;
}