问是否会TLE(luoguAC)
查看原帖
问是否会TLE(luoguAC)
509794
快乐的小男生楼主2021/11/25 12:54

问下各位这个会不会被大数据卡死

#include<cstdio> 
using namespace std;
int t,x,sum;
int cancall[10001001];
bool step[10001001];
inline bool pd(int x)
{
	int k;
	while(x)
	{
		k=x%10;
		if(k==7)
			return true;
		x/=10;
	}
	return false;
}
int main()
{
	scanf("%d",&t);
	for(int i=1;i<=10000001;++i)
	{
		if(pd(i)==true)
		{
			int point=i;
			while(point<10000001)
				step[point]=1,point+=i;
		}
		if(step[i]==0)
			++sum,cancall[sum]=i;
	}
	for(int i=1;i<=t;++i)
	{
		scanf("%d",&x);
		if(step[x]==1)
		{
			printf("-1\n");
			continue;
		}
		int l=1,r=sum;
		int mid;
		while(l<r)
		{
			mid=(l+r)/2;
			if(cancall[mid]==x)
				break;
			if(cancall[mid]>x)
				r=mid;
			else
				l=mid;
		}
		printf("%d\n",cancall[mid+1]);
	}
	return 0;
}
2021/11/25 12:54
加载中...