21分萌新求助!
查看原帖
21分萌新求助!
1007096
Handezheng楼主2023/12/19 21:47

为什么只有21分???


这道题难道不是用线性筛吗?
两层循环也没有TLE啊,为什么会WA?
代码:

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

#define int long long

const int N=1e6+5;

int n,m;
int l,r;
int f[N],p[N],c;
int ans;

void ola(int m){
   for(int i=2;i<=m;i++){
   	if(f[i]==0){
   		p[++c]=i;
   	}
   	for(int j=1;p[j]*i<=m&&j<=c;j++){
   		f[p[j]*i]=1;
   		if(i%p[j]==0) break;
   	}
   }
}

signed main(){

//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
   
   cin>>n>>m;
   ola(m);
   
   for(int k=1;k<=n;k++){
   	cin>>l>>r;
   	ans=0;
   	if(l<1||r>m){
   		cout<<"Crossing the line"<<endl;
   		continue;
   	}
   	for(int i=1;i<c;i++){
   		if(p[i]>r) break;
   		if(p[i]>l) ans++;
   	}
   	cout<<ans<<endl;
   }
   
//	fclose(stdin);
//	fclose(stdout);

   return 0;
}

实在搞不懂

2023/12/19 21:47
加载中...