为什么在9989899之后跳出循环即可避免TLE?
查看原帖
为什么在9989899之后跳出循环即可避免TLE?
91757
BlakrPander楼主2021/3/13 14:10

首先放出代码:

#include<bits/stdc++.h>
#include<time.h>
using namespace std;

const int MaxN=1e8+50;
bool judge[MaxN]={false};
int prime[MaxN]={0};

bool if_Mirrored_Num(int num);

int main(){
	//clock_t start,end;
	//start=clock();
	
	int L,R;
	int total=0,temp=0;
	cin>>L>>R;
	for(int i=2;i<MaxN;i++){ 	
		
		if(i>R)			//1
			break;
		
		if(i>R||i>9989899)//2
			break;
		
		if(!judge[i])
			prime[total++]=i;
		for(int j=0;j<total;j++){
			if(i*prime[j]>MaxN)
				break;	
			judge[i*prime[j]]=true;
			if(i%prime[j]==0)
				break;
		}
		if(temp!=total){
			if(prime[total-1]<=R&&prime[total-1]>=L&&if_Mirrored_Num(prime[total-1]))
				cout<<prime[total-1]<<endl;	
			temp=total;
		}
	}
	
	//end=clock();
	//double runtime=(double)(end-start)/CLOCKS_PER_SEC;
	//cout<<runtime;
	
	//system("pause");
	return 0;
}

bool if_Mirrored_Num(int num){
	int temp=0,num_1=num;
	for(;num_1!=0;){
		temp=temp*10+num_1%10;
		num_1/=10;
	}
	return temp==num;
}

其中,我标注了两个地方:

		if(i>R)	    	//1
			break;

		if(i>R||i>9989899)//2
			break;

此时输入为

 5 100000000

用1的判断条件的话,最后一个测试点就会TLE。而用2的判断条件时,在9989899之后跳出,则不会TLE。

而我个人测试了一下,用1的runtime大概比2的runtime慢了0.5秒左右,不是很理解这个问题。

2021/3/13 14:10
加载中...