题解 | #智乃的博弈游戏#

按照雨巨的思路对于商在[sqrt+1,n]暴力，对于[1,sqrt]分块，注意sqrt-1的商不一定是sqrt+1

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline void divide() {sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
// inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
inline ll Lsqrt(ll x) { ll L = 1,R = 2e9;while(L + 1 < R){ll M = (L+R)/2;if(M*M <= x) L = M;else R = M;}return L;}
void solve()
{
    int n,k;
    cin>>n>>k;
    int Sqrt = sqrt(n);
    vector<int> e;
    //注意商小于Sqrt的边界不一定是Sqrt-1
    int Bound = n/(Sqrt+1);
    for(int i=1;i<=Bound;++i)
    {
        e.push_back(n % i);
    }
    sort(e.begin(),e.end());
    //因为后面要用的Sum[n/(Sqrt+1)+1]来表示无解注意数组开的大小
    vector<ll> Sum(Bound+2);
    if(Bound >= 1)
    {
        Sum[Bound] = e[Bound - 1];
        for(int i=Bound-1;i>=1;--i) Sum[i] = Sum[i+1] + e[i - 1];
    }
    vector<PII> a(Sqrt + 1);
    //枚举商
    for(int i=1;i<=Sqrt;++i)
    {
        //找首项
        int Fir = n/i;
        int Last = n/(i+1);
        a[i].x = n % Fir, a[i].y = Fir - Last;
    }
    auto check = [&](int M)->pair<int,ll>
    {
        auto it = lower_bound(e.begin(),e.end(),M);
        int num = 0;
        ll res = 0;
        num += e.end() - it;
        res += Sum[Bound + 1 - (e.end() - it)];
        for(int i=1;i<=Sqrt;++i)
        {
            //对于商为i的查找有多少大于等于M的模数
            //注意此处的idx需要上取整
            int idx = (M - a[i].x + i - 1 + i)/i;
            //idx可能为负数
            idx = max(idx, 1);
            if(a[i].y >= idx) 
            {
                num += a[i].y - idx + 1;
                res += (((ll)2*a[i].x+(ll)(idx+a[i].y-2)*i)*(a[i].y-idx+1))/2;
            }
        }
        return {num, res};
    };
    int L = 0, R = n - 1;
    pair<int,ll> res;
    //左半边满足大于等于i的数>=k,答案为L
    while(L + 1 < R)
    {
        int M = (L + R)/2;
        res = check(M);
        if(res.x >= k) L = M;
        else R = M;
    }
    res = check(L);
    //因为统计的是>=L的和，所以可能统计了超过k项
    cout<<res.y - (ll)(res.x - k) * L <<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}