QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#149129#6740. FunctionUFRJWA 87ms4076kbC++20512b2023-08-24 02:05:122023-08-24 02:05:15

Judging History

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

  • [2023-08-24 02:05:15]
  • 评测
  • 测评结果:WA
  • 用时:87ms
  • 内存:4076kb
  • [2023-08-24 02:05:12]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

using lint = int64_t;

unordered_map<lint, lint> memo;

lint solve(lint x){
  if(x == 1) return 1;
  if(memo.count(x)) return memo[x];
  lint &ans = memo[x];
  ans = 1;
  for(lint a =1, b; a<=x; a=b+1){
    b = x / (x/a);
    lint A = max<lint>(2, a);
    lint B = min<lint>(b, 20210926);
    ans += ( (B-A+1) % 998244353 )* solve(x/a);
    ans %= 998244353;
  }
  return ans;
}

int main(){
  lint n; cin>>n;
  cout<<solve(n)<<"\n";


}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3436kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

2

output:

2

result:

ok 1 number(s): "2"

Test #3:

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

input:

100

output:

949

result:

ok 1 number(s): "949"

Test #4:

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

input:

10

output:

19

result:

ok 1 number(s): "19"

Test #5:

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

input:

1000

output:

48614

result:

ok 1 number(s): "48614"

Test #6:

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

input:

10000

output:

2602393

result:

ok 1 number(s): "2602393"

Test #7:

score: 0
Accepted
time: 2ms
memory: 3528kb

input:

100000

output:

139804054

result:

ok 1 number(s): "139804054"

Test #8:

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

input:

1000000

output:

521718285

result:

ok 1 number(s): "521718285"

Test #9:

score: 0
Accepted
time: 17ms
memory: 3780kb

input:

10000000

output:

503104917

result:

ok 1 number(s): "503104917"

Test #10:

score: -100
Wrong Answer
time: 87ms
memory: 4076kb

input:

100000000

output:

123625420

result:

wrong answer 1st numbers differ - expected: '198815604', found: '123625420'