QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#859229 | #9680. 数字变换 | JohnAlfnov | 12 | 203ms | 88532kb | C++17 | 1.9kb | 2025-01-17 16:39:45 | 2025-01-17 16:39:51 |
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[5000005];
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[wz[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: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 26ms
memory: 42832kb
input:
1 10 3
output:
3 11 11 13 14 16 15 18 19 16
result:
wrong answer 1st numbers differ - expected: '4', found: '3'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 12
Accepted
Test #11:
score: 12
Accepted
time: 203ms
memory: 87940kb
input:
3000000000 3000000000 4
output:
194829
result:
ok 1 number(s): "194829"
Test #12:
score: 12
Accepted
time: 191ms
memory: 88532kb
input:
2677114440 2677114440 4
output:
3247949
result:
ok 1 number(s): "3247949"
Test #13:
score: 12
Accepted
time: 90ms
memory: 58772kb
input:
559172255 559172255 3
output:
87
result:
ok 1 number(s): "87"
Test #14:
score: 12
Accepted
time: 121ms
memory: 70832kb
input:
1829400271 1829400271 2
output:
5
result:
ok 1 number(s): "5"
Test #15:
score: 12
Accepted
time: 48ms
memory: 48636kb
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:
0%