QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#862767 | #9680. 数字变换 | SimonLJK | 32 | 3542ms | 126304kb | C++17 | 1.0kb | 2025-01-19 09:38:10 | 2025-01-19 09:38:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int N=5e6+999;
int l,r,b,n;
int p[N],cntp,vis[N];
void init(){
for(int i=2;i<=n;i++){
if(!vis[i])
vis[i]=p[++cntp]=i;
for(int j=1;j<=cntp;j++){
if(i*p[j]>n||vis[i]<p[j]) break;
vis[i*p[j]]=p[j];
}
}
}
int f[N],g[N],ans[N];
void add(int &x,int y){
if((x+=y)>=mod) x-=mod;
}
void calc(){
for(int i=l;i<=r;i++)
add(ans[i],f[i]);
return;
}
void dp(){
for(int i=1;i<=cntp;i++)
for(int j=p[i];j<=n;j+=p[i])
add(g[j],g[j/p[i]]);
for(int i=1;i<=n;i++){
add(g[i],f[i-1]);
add(g[i],f[i+1]);
add(g[i],mod-f[i]);
}
memcpy(f,g,sizeof(f));
return;
}
void solve1(){
n=r+50;
init();
f[1]=g[1]=1;
calc();
for(int i=1;i<=b;i++){
dp();
calc();
}
for(int i=l;i<=r;i++)
cout<<ans[i]<<" ";
return;
}
void solve2(){
return;
}
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cin>>l>>r>>b;
if(r<=5000000&&b<=40) solve1();
else solve2();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 9ms
memory: 45040kb
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: 25ms
memory: 46576kb
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: 4ms
memory: 45300kb
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: 27ms
memory: 46064kb
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: 518ms
memory: 62468kb
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: 515ms
memory: 63000kb
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: 196ms
memory: 49408kb
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: 8
Accepted
Dependency #2:
100%
Accepted
Test #8:
score: 8
Accepted
time: 3444ms
memory: 126304kb
input:
4782535 4812535 40
output:
364397686 165873203 574344543 635260147 643680700 470212193 293286338 86597296 949547162 406431028 409208995 879294450 362298346 814274913 938440591 364822215 145690007 153133848 353411991 83011067 792144215 874639624 932112052 992808929 19052833 475247393 458224951 594473504 963947504 246877880 258...
result:
ok 30001 numbers
Test #9:
score: 8
Accepted
time: 3542ms
memory: 124612kb
input:
4970000 5000000 40
output:
388505040 319193752 303995931 721356438 674101808 587396878 575493425 118848598 713635771 819216980 422508264 990658212 423103666 59181390 763452803 35511687 136729844 477075728 557181150 908342726 539083563 408016211 499540165 320257704 727475398 304007021 951214389 915018848 897223056 983417047 91...
result:
ok 30001 numbers
Test #10:
score: 8
Accepted
time: 684ms
memory: 68340kb
input:
1318577 1348577 40
output:
830660372 964578913 889681253 808462744 639764929 300482893 764823065 300856459 526801385 973921344 746603566 833215730 129286529 547559226 232599327 593770921 542016604 308259906 584254182 287063296 897043650 566545458 540624702 725152930 829184497 158961870 490270826 365349718 460992689 435577466 ...
result:
ok 30001 numbers
Subtask #4:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 3584kb
input:
3000000000 3000000000 4
output:
result:
wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements
Subtask #5:
score: 0
Wrong Answer
Dependency #3:
100%
Accepted
Test #16:
score: 0
Wrong Answer
time: 0ms
memory: 3456kb
input:
99970000 100000000 100
output:
result:
wrong answer Answer contains longer sequence [length = 30001], but output contains 0 elements
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
0%