9RE 1AC 是哪里的细节没处理好吗
查看原帖
9RE 1AC 是哪里的细节没处理好吗
1276544
luoguerepp楼主2024/3/24 16:30

一头雾水,不知道为什么最后的j - l + 1会有负数

#include<cstdio>
#include<cstring>

const int N = 5e4 + 10;
typedef long long LL;

int l,r;
int primes[N],idx;
bool vis[N];

void get_primes(){
    for(int i = 2; i < N; ++i){
        if(!vis[i]) primes[idx++] = i;
        for(int j = 0; primes[j] < N / i; ++j){
            vis[i * primes[j]] = true;
            if(i % primes[j] == 0)  break;
        }
    }
}
int main(){
    scanf("%d%d",&l,&r);
    
    get_primes();
    memset(vis,0,sizeof vis);
    
    if(l == 1)  l++;
    for(int i = 0; i < idx; ++i){
        int p = primes[i];
        int st = (l + p - 1) / p * p > 2 * p ? (1 + p - 1) / p * p : 2 * p;
        for(LL j = st; j <= r; j += p) vis[j - l + 1] = true;
    }
    
    LL ans = 0;
    for(LL i = l; i <= r; ++i)  
		if(!vis[i]) ans++;
    printf("%lld",ans);
    
    return 0;
}
2024/3/24 16:30
加载中...