QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#768791 | #6740. Function | DGH_Didi | TL | 198ms | 9900kb | C++20 | 2.9kb | 2024-11-21 14:30:11 | 2024-11-21 14:30:11 |
Judging History
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