QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#347465 | #6740. Function | wtz2333 | WA | 9ms | 3732kb | C++17 | 1.0kb | 2024-03-09 13:55:17 | 2024-03-09 13:55:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mo = 998244353;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
map<int,int> mp;
auto calc = [&](auto self,int x) -> ll {
if(x == 0)return 0;
if(mp[x]) return mp[x];
ll l = 2,r;ll ans = 1;
while(l <= min(20210926,x)){
r = x / (x / l);
ans += 1ll * (r - l + 1) * self(self,x / l) % mo;
l = r + 1;
}
return mp[x] = ans;
};
if(n > 1) {
cout << calc(calc,n) << endl;
}else {
ll ans = 0;
int cnt = 1;
vector<int> f(n + 1,1);
for(int i = n - 1;i >= 1;i --) {
for(int j = 2 * i;j <= n;j += i) {
f[i] += f[j];
// cerr << f[j] << " ";
}//cerr << endl;
}
cout << f[1] << endl;
}
}
// n / 20210926 <= k
/// 1 2 3 4 5 6 7 8
// 14 5 2 2 1 1 1 1
// 13 4 1 1 0 0 0 0
// 12 3 0 0 0 0 0 0
//
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
2
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
100
output:
949
result:
ok 1 number(s): "949"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
10
output:
19
result:
ok 1 number(s): "19"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
1000
output:
48614
result:
ok 1 number(s): "48614"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
10000
output:
2602393
result:
ok 1 number(s): "2602393"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
100000
output:
139804054
result:
ok 1 number(s): "139804054"
Test #8:
score: -100
Wrong Answer
time: 9ms
memory: 3732kb
input:
1000000
output:
-82261483
result:
wrong answer 1st numbers differ - expected: '521718285', found: '-82261483'