QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#859229#9680. 数字变换JohnAlfnov12 203ms88532kbC++171.9kb2025-01-17 16:39:452025-01-17 16:39:51

Judging History

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

  • [2025-01-17 16:39:51]
  • 评测
  • 测评结果:12
  • 用时:203ms
  • 内存:88532kb
  • [2025-01-17 16:39:45]
  • 提交

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%