QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#347465#6740. Functionwtz2333WA 9ms3732kbC++171.0kb2024-03-09 13:55:172024-03-09 13:55:21

Judging History

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

  • [2024-03-09 13:55:21]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:3732kb
  • [2024-03-09 13:55:17]
  • 提交

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'