1 条题解

  • 0
    @ 2026-8-1 21:07:54
    #include <bits/stdc++.h>
    #define int long long
    #define mod 998244353
    using namespace std;
    int n, f[1000005];
    unordered_map<int, int> mp;
    void init() {
        f[1] = 1;
    
        for (int i = 1; i <= 1000000; i++)
            for (int j = i + i; j <= 1000000; j += i)
                f[j] = (f[j] + f[i]) % mod;
    
        for (int i = 1; i <= 1000000; i++)
            f[i] = (f[i] + f[i - 1]) % mod;
    }
    int solve(int x) {
        if (x <= 1000000)
            return f[x];
    
        if (mp.count(x))
            return mp[x];
        else {
            int ans = 1;
    
            for (int l = 2, r; l <= x; l = r + 1) {
                r = x / (x / l);
                ans = (ans + (r - l + 1) * solve(x / l)) % mod;
            }
    
            return mp[x] = ans;
        }
    }
    signed main() {
        init();
        cin >> n;
        cout << solve(n);
        return 0;
    }
    
    • 1

    信息

    ID
    9761
    时间
    2000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者