算法

(数论分块) $O(\sqrt{k})$

$\displaystyle \sum_{i = 1}^n k \% i = \sum_{i=1}^n (k - i * \lfloor \frac{k}{i}\rfloor) = nk - \sum_{i = 1}^n i * \lfloor\frac{k}{i}\rfloor$

其中 $\displaystyle \sum_{i = 1}^n i * \lfloor\frac{k}{i}\rfloor$ 的部分可以用数论分块来求。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::min;
using ll = long long;

int main() {
    ll n, k;
    cin >> n >> k;

    ll ans = n * k;
    for (ll i = 1; i <= n; ++i) {
        ll t = k / i;
        ll j = t ? min(k / t, n) : n;
        ans -= (j - i + 1) * t * (i + j) / 2;
        i = j;
    }

    cout << ans << '\n';

    return 0;
}