QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#859285 | #9680. 数字变换 | JohnAlfnov | 100 ✓ | 3760ms | 310968kb | C++17 | 1.9kb | 2025-01-17 17:02:55 | 2025-01-17 17:03:05 |
Judging History
answer
#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
long long l,r;
int B,t=0;
unordered_set<long long>se;
long long p[3000005];
int wz[30005],ans[30005];
int f[3000005],g[3000005];
bool s[10000005];
int d[1000005],zx[10000005],tot=0;
const int T=5e6;
void print(int N){
s[1]=1;
for(int i=2;i<=N;++i){
if(!s[i])d[++tot]=i,zx[i]=i;
for(int j=1;j<=tot&&i*d[j]<=N;++j){
s[i*d[j]]=1;zx[i*d[j]]=min(zx[i],d[j]);
if(i%d[j]==0)break;
}
}
}
unordered_map<long long,int>m1;
pair<long long,pair<int,int>>pi[10000005];
int tt=0;
void jia(long long x,int y){
if(m1.find(p[y]/x)==m1.end())return;
pi[++tt]=make_pair(x,make_pair(y,m1[p[y]/x]));
}
int main(){
scanf("%lld%lld%d",&l,&r,&B);
long long rr=1e18;
for(long long L=1;L<=l;){
long long R=min(l/(l/L),r/(r/L));
for(long long x=max(1ll,l/L-B);x<=r/L+B&&x<rr;++x){
se.emplace(x);
}
rr=l/L-B;
L=R+1;
}
for(auto cu:se)p[++t]=cu;
sort(p+1,p+t+1);
for(int i=1;i<=t;++i){
if(p[i]>=l&&p[i]<=r)wz[p[i]-l]=i;
m1[p[i]]=i;
}
f[1]=1;if(l<=1)ans[1-l]=1;
print(T);
for(int i=1;i<=t;++i){
long long pp=p[i];
if(pp>T){
for(int j=1;j<=tot&&d[j]<=pp/d[j];++j){
int z=d[j];if(pp%z)continue;
jia(z,i);
while(pp%z==0)pp/=z;
if(pp<=T)break;
}
}
if(pp<=T){
while(pp>1){
int z=zx[pp];
while(pp%z==0)pp/=z;
jia(z,i);
}
}else{
jia(pp,i);
}
}
p[0]=-1;
sort(pi+1,pi+tt+1);
while(B--){
for(int i=1;i<=t;++i)g[i]=f[i];
for(int i=1;i<=tt;++i){
auto pp=pi[i].second;
g[pp.first]=(g[pp.first]+g[pp.second])%mod;
}
for(int i=1;i<=t;++i)if(f[i]){
g[i]=(g[i]-f[i]+mod)%mod;
if(p[i+1]==p[i]+1)g[i+1]=(g[i+1]+f[i])%mod;
if(p[i-1]==p[i]-1)g[i-1]=(g[i-1]+f[i])%mod;
}
for(int i=1;i<=t;++i)f[i]=g[i];
for(int i=0;i<=r-l;++i)ans[i]=(ans[i]+f[wz[i]])%mod;
}
for(int i=0;i<=r-l;++i)printf("%d ",ans[i]);
return 0;
}
详细
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 26ms
memory: 42832kb
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: 21ms
memory: 42668kb
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: 24ms
memory: 40788kb
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: 24ms
memory: 40780kb
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: 134ms
memory: 63304kb
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: 132ms
memory: 63012kb
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: 98ms
memory: 58136kb
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: 182ms
memory: 73848kb
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: 192ms
memory: 76284kb
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: 150ms
memory: 66948kb
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: 12
Accepted
Test #11:
score: 12
Accepted
time: 205ms
memory: 89808kb
input:
3000000000 3000000000 4
output:
194829
result:
ok 1 number(s): "194829"
Test #12:
score: 12
Accepted
time: 184ms
memory: 82324kb
input:
2677114440 2677114440 4
output:
3247949
result:
ok 1 number(s): "3247949"
Test #13:
score: 12
Accepted
time: 84ms
memory: 59064kb
input:
559172255 559172255 3
output:
87
result:
ok 1 number(s): "87"
Test #14:
score: 12
Accepted
time: 122ms
memory: 74068kb
input:
1829400271 1829400271 2
output:
5
result:
ok 1 number(s): "5"
Test #15:
score: 12
Accepted
time: 48ms
memory: 45524kb
input:
249371392 249371392 1
output:
1
result:
ok 1 number(s): "1"
Subtask #5:
score: 15
Accepted
Dependency #3:
100%
Accepted
Test #16:
score: 15
Accepted
time: 865ms
memory: 116760kb
input:
99970000 100000000 100
output:
299847561 426721677 328903860 885015272 409812819 288225868 504259988 606093831 591725363 219354824 41647194 666401507 745732204 433193237 869825648 723267671 913018348 216254698 650311284 7141655 502176694 577292545 487415657 262361880 697212396 426460634 169270371 752060813 328922684 389507690 588...
result:
ok 30001 numbers
Test #17:
score: 15
Accepted
time: 651ms
memory: 105840kb
input:
50611321 50641321 100
output:
342415238 241519789 993636911 970641734 500727769 111142137 302855752 813200207 657210035 261517519 253348522 787092524 822829533 292392507 2185897 815346072 125676240 484210436 567377469 660433911 662495991 270093741 505462548 465175271 411504024 731199062 484669606 202643211 858298704 768389613 14...
result:
ok 30001 numbers
Test #18:
score: 15
Accepted
time: 854ms
memory: 110436kb
input:
98670000 98700000 100
output:
794004969 139311691 321944895 438081915 420893841 66108028 360788206 387931994 740746675 307070138 477456496 588831984 468605563 635258566 453807317 986427496 187587850 75055147 66571623 70921192 18085871 173131905 490168620 17275180 345588992 913668493 47574492 918346611 352821308 40237235 14325243...
result:
ok 30001 numbers
Subtask #6:
score: 23
Accepted
Dependency #5:
100%
Accepted
Test #19:
score: 23
Accepted
time: 2332ms
memory: 204036kb
input:
999970000 1000000000 100
output:
5670933 833737828 314392369 423522639 753322405 656472437 438982700 867301927 760286456 247136279 307805571 414421595 893288368 380483666 40490620 463013482 40584519 464260005 460239560 13855719 165237083 246976670 375775054 778597542 894079068 350083553 929372176 177960563 808245763 560832085 70935...
result:
ok 30001 numbers
Test #20:
score: 23
Accepted
time: 1502ms
memory: 163040kb
input:
381731639 381761639 100
output:
142430785 947737302 195693591 57545719 183947806 123247460 662672308 646830905 251007674 799633240 575931165 917010755 529990255 791241869 23830680 766967963 917495024 256375350 656853653 166940050 917727813 544640274 416909499 714094883 508705483 995028472 171182143 612852002 107678818 162956438 93...
result:
ok 30001 numbers
Test #21:
score: 23
Accepted
time: 2338ms
memory: 203664kb
input:
986970000 987000000 100
output:
256209602 459410757 616919102 240643858 316109191 405872582 785202983 352397259 595268152 260686976 764841229 182321782 342552139 717006721 208951090 127877651 222349936 890227218 401789063 480599770 878539388 517676721 39757956 18889234 793767677 481206630 557390201 121846406 543016846 220628013 55...
result:
ok 30001 numbers
Subtask #7:
score: 18
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #22:
score: 18
Accepted
time: 3760ms
memory: 310968kb
input:
2999970000 3000000000 100
output:
430210442 343313384 799745399 776926287 486284032 511483228 944771506 209440509 304039725 174819237 174376659 198643465 718983043 65202513 913036016 687050906 626938463 827336171 401770106 619288148 88910977 862449583 845201927 856185985 534678313 183145800 132542503 448542999 242347498 14212845 463...
result:
ok 30001 numbers
Test #23:
score: 18
Accepted
time: 3258ms
memory: 290252kb
input:
2192732737 2192762737 100
output:
733814200 331482816 103153712 589599963 761106758 398433327 678959952 789527139 21685846 522551843 63148462 905314181 134208235 699329089 289429405 824510575 750197623 636068914 839087865 788372920 767408034 573968900 256229188 928013124 335826814 13586076 960696352 642080571 330391624 149553034 673...
result:
ok 30001 numbers
Test #24:
score: 18
Accepted
time: 3754ms
memory: 310680kb
input:
2986970000 2987000000 100
output:
681351109 83623297 947120936 906900101 377555998 131410323 292516575 205213905 155979946 113601183 211060529 208005957 551777008 988058525 161506067 735511163 611360205 977760576 953212745 779749861 237267775 68787469 76209862 357213623 290848094 712795298 303873926 309570406 912601805 92497160 5514...
result:
ok 30001 numbers