本地1.5s,洛谷上才300ms
查看原帖
本地1.5s,洛谷上才300ms
748157
real_CCF楼主2023/11/16 20:13

是本地dev太慢的缘故吗?还是因为你谷神速测评机?CCF机子大概跑多少?

#include<bits/stdc++.h>
#define N 10000105
#define int long long
using namespace std;
int T,n=1e7+100,fnt,num[N],pri[N],cnt,ans[N]={};
bool v[N],p[N];
void read(int &x){
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}
void OLS(int x){
	for(int i=1;i<=x;i++) p[i]=true;
	p[0]=p[1]=false;
	for(int i=2;i<=x;i++){
		if(p[i]) pri[++cnt]=i;
		for(int j=1;j<=cnt&&i*pri[j]<=x;j++){
			p[i*pri[j]]=false;
			if(i%pri[j]==0) break;
		}
	}
}
signed main(){
	OLS(n);
	cnt=0;
	for(int i=1,k;i<=n;i++){
		k=i;
		while(k){
			if(k%10==7){
				v[i]=true;
				break;
			}
			k/=10;
		}
		v[i]^=1;
		if(!v[i]) num[++cnt]=i;
	}
	for(int i=1;i<=cnt;i++){
		for(int j=1;num[i]*j<=n;j++){
			v[num[i]*j]=false;
		}
	}
	cnt=0;
	for(int i=1;i<=n;i++){
		if(v[i]) num[++cnt]=i;
	}
	read(T);
	int qwq,l,r,mid;
	while(T--){
		read(qwq);
		if(!v[qwq]){
			printf("-1\n");
			continue;
		}
		l=1,r=cnt;
		while(l<r){
			mid=l+r>>1;
			if(num[mid]>qwq) r=mid;
			else l=mid+1;
		}
		printf("%lld\n",num[l]);
	}
	return 0;
}
/*
10 1
5 2 3 4 5 7
3 6 7 9
3 7 8 9
3 8 9 6
1 7
2 9 10
2 10 9
0
0
0

*/
2023/11/16 20:13
加载中...