QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#768791#6740. FunctionDGH_DidiTL 198ms9900kbC++202.9kb2024-11-21 14:30:112024-11-21 14:30:11

Judging History

你现在查看的是最新测评结果

  • [2024-11-21 14:30:11]
  • 评测
  • 测评结果:TL
  • 用时:198ms
  • 内存:9900kb
  • [2024-11-21 14:30:11]
  • 提交

answer

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
using i64 = long long;

template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    while (b) {
        if (b & 1) {
            res = res * a;
        }
        b >>= 1;
        a = a * a;
    }
    return res;
}

template<i64 P>
struct ModInt {
    i64 x;
    constexpr ModInt() : x{} {}
    constexpr ModInt(i64 x) : x{norm(x % P)} {}
    constexpr i64 norm(i64 x) const {
        if (x >= P) {
            x -= P;
        } else if (x < 0) {
            x += P;
        }
        return x;
    }
    constexpr i64 val() const {
        return x;
    }
    constexpr ModInt operator-() const {
        ModInt res;
        res.x = norm(P - x);
        return res;
    }
    constexpr ModInt inv() const {
        return power(*this, P - 2);
    }
    constexpr ModInt operator+=(ModInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr ModInt operator-=(ModInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr ModInt operator*=(ModInt rhs) & {
        x = norm(x * rhs.x % P);
        return *this;
    }
    constexpr ModInt operator/=(ModInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr ModInt operator+(ModInt lhs, ModInt rhs) {
        ModInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr ModInt operator-(ModInt lhs, ModInt rhs) {
        ModInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr ModInt operator*(ModInt lhs, ModInt rhs) {
        ModInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr ModInt operator/(ModInt lhs, ModInt rhs) {
        ModInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr bool operator==(ModInt lhs, ModInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(ModInt lhs, ModInt rhs) {
        return lhs.val() != rhs.val();
    }
    friend constexpr istream &operator>>(istream &is, ModInt &a) {
        i64 v;
        is >> v;
        a = ModInt(v);
        return is;
    }
    friend constexpr ostream &operator<<(ostream &os, const ModInt &a) {
        return os << a.val();
    }
};

using mint = ModInt<998244353>;
i64 n;
map<int, mint> mem;
vector<int> arr;

mint f(i64 x) {
    if (mem.count(x)) {
        return mem[x];
    }
    // arr.push_back(x);
    mint res = 1;
    for (int i = 2; i <= 20210926; i++) {
        if (x * i <= n) {
            res += f(x * i);
        } else {
            break;
        }
    }
    return mem[x] = res;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    cout << f(1) << endl;
    // sort(arr.begin(), arr.end());
    // for (int x : arr) {
    //     cout << x << " ";
    // }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3664kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

2

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

100

output:

949

result:

ok 1 number(s): "949"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

10

output:

19

result:

ok 1 number(s): "19"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

1000

output:

48614

result:

ok 1 number(s): "48614"

Test #6:

score: 0
Accepted
time: 11ms
memory: 4332kb

input:

10000

output:

2602393

result:

ok 1 number(s): "2602393"

Test #7:

score: 0
Accepted
time: 198ms
memory: 9900kb

input:

100000

output:

139804054

result:

ok 1 number(s): "139804054"

Test #8:

score: -100
Time Limit Exceeded

input:

1000000

output:


result: