H 数论

思路

留意到每个对 $(n, k)$ 中，$k$ 是独立的，故把每个 $k$ 分开分析。

刚开始我没有留意到 $n$ 一定是 $n \mod k \equiv 0$ 或 $n \mod k \equiv 1$ 的，后面才观察到。

但其实这个性质很容易观察： 1、根据性质1、2，所有 $1 \le n \le N,n \mod k \equiv 1$ 的数 $n$, $(n, k)$ 是合法的 2、根据性质3，所有 $1 \le n \le N,n \mod k \equiv 0$ 的数 $n$, $(n, k)$ 是合法的

因此，当$ k\neq 1,$ $1 \le i \le n $ 时，$(i, k)$ 中合法的对有 $\lfloor \frac{n}{k} \rfloor + \lfloor \frac{n-1}{k} \rfloor + 1$ 个 特别的，当 $k = 1$ 时，有 $n$ 个合法对。

因此 $f(n, k) = n + \sum \limits_{i=2}^{k}(\lfloor \frac{n}{k} \rfloor + \lfloor \frac{n-1}{k} \rfloor + 1)$，使用简单的数论分块即可 $O(\sqrt{k})$ 解决问题。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;

ll solve(ll n, ll k) {
    ll ans = n % MOD;
    for (ll l = 2, r; l <= k; l = r + 1) {
        ll r1 = k, r2 = k;
        if (n / l)           r1 = n / (n / l);
        if ((n - 1) / l)     r2 = (n - 1) / ((n - 1) / l);
        r = min(k, min(r1, r2));
        ans = (ans + (r - l + 1) % MOD * (n / l + (n - 1) / l + 1)) % MOD;
    }
    return ans;
}

int main() {
    ll n, k;
    scanf("%lld%lld", &n, &k);
    printf("%lld\n", solve(n, k));
    return 0;
}