题解 | #袋鼠赢家#

C

数论计算，用于找到第k个有序数对并计算其平方和的特定值

代码要解决的核心问题是：找到所有正整数对 (i, j) 按 i×j 排序后的第k对，并计算所有满足 i×j ≤ T 的数对 (i² × j²) 的和模 998244353。 modinv(a, m) - 模逆元计算 使用扩展欧几里得算法计算模逆元，用于除法操作。 sum_sq_mod(n) - 平方和公式 计算 1² + 2² + ... + n² 模 MOD，使用公式：

count_tau(T) - 计算数对数量 计算满足 i×j ≤ T 的正整数对 (i, j) 的数量，即：

使用数论分块优化，避免O(T)复杂度。 sum_tau_m2_mod(M) - 计算平方和

计算所有满足 i×j ≤ M 的数对 (i² × j²) 的和：
同样使用数论分块优化。

shixian 第一步：二分查找找到第k个数对对应的T

while (count_tau(hi) < k) hi <<= 1;
while (lo < hi) {
    ll mid = (lo + hi) / 2;
    if (count_tau(mid) >= k) hi = mid;
    else lo = mid + 1;
}
ll T = lo;

第二步：定位第k个数对

ll c_prev = count_tau(T - 1);
ll r = k - c_prev;  // 在乘积等于T的数对中的排名

第三步：计算结果

ll sum_before = sum_tau_m2_mod(T - 1);  // 所有i×j < T的平方和
ll ans = (sum_before + r * T²) % MOD;   // 加上第k个位置的贡献

复杂度

• 时间复杂度：O(√T log T) - 数论分块 + 二分查找
• 空间复杂度：O(1) - 只使用常数空间

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
ll modinv(ll a, ll m) {
    ll m0 = m, t, q;
    ll x0 = 0, x1 = 1;
    if (m == 1) return 0;
    while (a > 1) {
        q = a / m;
        t = m; m = a % m; a = t;
        t = x0; x0 = x1 - q * x0; x1 = t;
    }
    if (x1 < 0) x1 += m0;
    return x1;
}
ll sum_sq_mod(ll n) {
    n %= MOD;
    ll a = n * ((n + 1) % MOD) % MOD;
    ll b = (2 * n + 1) % MOD;
    ll inv6 = modinv(6, MOD);
    return a * b % MOD * inv6 % MOD;
}
ll count_tau(ll T) {
    if (T <= 0) return 0;
    ll res = 0;
    ll d = 1;
    while (d <= T) {
        ll q = T / d;
        ll r = T / q;
        res += q * (r - d + 1);
        d = r + 1;
    }
    return res;
}
ll sum_tau_m2_mod(ll M) {
    if (M <= 0) return 0;
    ll res = 0;
    ll d = 1;
    while (d <= M) {
        ll q = M / d;
        ll r = M / q;
        ll sum_d2 = (sum_sq_mod(r) - sum_sq_mod(d - 1) + MOD) % MOD;
        ll s2q = sum_sq_mod(q);
        res = (res + sum_d2 * s2q % MOD) % MOD;
        d = r + 1;
    }
    return res;
}

int main() {
    ll k;
    cin >> k;
    ll lo = 1, hi = 1;
    while (count_tau(hi) < k) hi <<= 1;
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        if (count_tau(mid) >= k)
            hi = mid;
        else
            lo = mid + 1;
    }
    ll T = lo;
    ll c_prev = count_tau(T - 1);
    ll r = k - c_prev;
    ll sum_before = sum_tau_m2_mod(T - 1);
    ll ans = (sum_before + r % MOD * (T % MOD) % MOD * (T % MOD) % MOD) % MOD;
    cout << ans << "\n";
    return 0;
}