神仙思路与证明

这道题可以将式子化简为：

\[ nk-\sum_{i=1}^{n} \lfloor \frac{k}{i} \rfloor * i \]

第一部分乘积即可，第二部分直觉告诉我们\(\lfloor \frac{k}{i} \rfloor\)在一段连续的\(i\)上会相等，也就是说，是分段的。每一段的和可以直接用等差数列来求就行。我们来探究一下段区间的左右端点。我们假设目标区间是\([i,?]\)，那么这一段区间的值肯定就是\(\lfloor \frac{k}{i} \rfloor\)，反求一下那么右端点就是\( \lfloor \frac{k}{\lfloor \frac{k}{i} \rfloor} \rfloor \)。可以证明右端点大于等于左端点。等差数列求和即可。

代码

// BZ1257.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, k;
int main()
{
    scanf("%lld%lld", &n, &k);
    ll ans = n * k, gx;
    for (int x = 1; x <= n; x = gx + 1)
    {
        gx = (k / x) ? min(k / (k / x), n) : n;
        // x ~ gx same;
        ans -= (k / x) * (gx - x + 1) * (gx + x) / 2;
    }
    printf("%lld", ans);
    return 0;
}