QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#859514#9680. 数字变换lgvc36 5364ms942152kbC++231.1kb2025-01-17 20:10:362025-01-17 20:10:37

Judging History

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

  • [2025-01-17 20:10:37]
  • 评测
  • 测评结果:36
  • 用时:5364ms
  • 内存:942152kb
  • [2025-01-17 20:10:36]
  • 提交

answer

#include <bits/stdc++.h>
#define MOD 998244353
#define LL long long
LL L,R;
int B,vq[42][2000109];
std::vector<int> tq[5000109];
inline int id(LL x) {
    if(x<=1000000) return x;
    int le=R/x;
    if(le==0||R/le-x>x-R/(le+1)) le++;
    return ((R)/le-x+102)*3000+le+1000009;
}
int fd(LL x,int y) {
    if(x==0) return 0;
    if(y==0) {
        if(x==1) return 1;
        return 0;
    }
    if(vq[y][id(x)]!=-1) return vq[y][id(x)];
    int as=fd(x-1,y-1)+fd(x+1,y-1);
    if(x==1) as++;
    as%=MOD;
    if(x<=5000100) {
        for(int i=0;i<tq[x].size();i++) {
            as=(as+fd(tq[x][i],y-1))%MOD;
        }
    } else {
        for(int i=1;1ll*i*i<=x;i++) {
            if(x%i) continue;
            if(i<x) as=(as+fd(i,y-1))%MOD;
            if(1ll*i*i!=x&&(i>1)) as=(as+fd(x/i,y-1))%MOD;
        }
    }
    vq[y][id(x)]=as;
    return as;
}
signed main(void) {
    memset(vq,-1,sizeof(vq));
    scanf("%lld %lld %d",&L,&R,&B);
    for(int i=1;i<=5000100;i++) {
        for(int j=2*i;j<=5000100;j+=i) {
            tq[j].push_back(i);
        }
    }
    for(LL i=L;i<=R;i++) {
        printf("%d ",fd(i,B));
    }
}

详细

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 4754ms
memory: 942116kb

input:

1 10 3

output:

4 10 11 13 14 16 15 18 19 16 

result:

ok 10 numbers

Test #2:

score: 6
Accepted
time: 4768ms
memory: 942080kb

input:

1 10 10

output:

1446 3555 5399 8364 9365 13867 13268 18455 18559 22035 

result:

ok 10 numbers

Test #3:

score: 6
Accepted
time: 4866ms
memory: 942152kb

input:

1 10 1

output:

1 2 1 1 1 1 1 1 1 1 

result:

ok 10 numbers

Test #4:

score: 6
Accepted
time: 4802ms
memory: 942108kb

input:

4 9 10

output:

8364 9365 13867 13268 18455 18559 

result:

ok 6 numbers

Subtask #2:

score: 18
Accepted

Dependency #1:

100%
Accepted

Test #5:

score: 18
Accepted
time: 5361ms
memory: 942024kb

input:

970000 1000000 40

output:

503190413 403501814 423543367 667735332 309717676 941521375 469059575 651585751 638081530 319769570 829344038 710448046 491906657 837995934 191992080 435477208 965318020 224310119 82608430 311469551 397529653 845900371 993051834 218739898 720518121 555742487 850145833 86074414 994934100 233037792 83...

result:

ok 30001 numbers

Test #6:

score: 18
Accepted
time: 5364ms
memory: 942152kb

input:

961235 991235 40

output:

726112142 872781888 864415992 271278585 161740406 328072996 78782063 87302065 34440839 496440232 20023252 186342396 764720954 729734275 738722871 935566953 929337897 876835483 50567341 207158528 584651187 436141466 570964468 351740029 722550019 982425596 33848740 853163527 651698124 526627241 675694...

result:

ok 30001 numbers

Test #7:

score: 18
Accepted
time: 5174ms
memory: 942152kb

input:

222672 252672 40

output:

631342631 757879799 692055601 186757611 650530712 706722357 916976233 819581990 264205227 549042234 803974629 75845131 29698194 175213976 499651702 699984450 376334876 686068237 257396075 368343435 360038977 718193111 387980917 173929086 672211730 117954620 277698487 337486141 473242448 412398980 93...

result:

ok 30001 numbers

Subtask #3:

score: 0
Runtime Error

Dependency #2:

100%
Accepted

Test #8:

score: 0
Runtime Error

input:

4782535 4812535 40

output:


result:


Subtask #4:

score: 12
Accepted

Test #11:

score: 12
Accepted
time: 4826ms
memory: 942028kb

input:

3000000000 3000000000 4

output:

194829 

result:

ok 1 number(s): "194829"

Test #12:

score: 12
Accepted
time: 4907ms
memory: 942152kb

input:

2677114440 2677114440 4

output:

3247949 

result:

ok 1 number(s): "3247949"

Test #13:

score: 12
Accepted
time: 4852ms
memory: 942124kb

input:

559172255 559172255 3

output:

87 

result:

ok 1 number(s): "87"

Test #14:

score: 12
Accepted
time: 4843ms
memory: 942152kb

input:

1829400271 1829400271 2

output:

5 

result:

ok 1 number(s): "5"

Test #15:

score: 12
Accepted
time: 4875ms
memory: 942024kb

input:

249371392 249371392 1

output:

1 

result:

ok 1 number(s): "1"

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%