LOJ6235 区间素数个数（min_25筛）

题目链接：LOJ

题目大意：看到题目名字应该都知道是啥了吧。

$1le Nle 10^{11}$。

---

阉割版 min_25 筛。发现答案实际上就是 min_25 筛中 $g(N,pl)$ 的值。（取次数 $k=0$ 即可）

在这里再写一遍式子。（用久了应该要背了）

$g(n,0)=n-1$

$g(n,j)=egin{cases}g(n,j-1)&p_j^2>n\g(n,j-1)-(g(lfloordfrac{n}{p_j} floor,j)-(j-1))&p_j^2le nend{cases}$

直接算即可。时间复杂度 $O(frac{N^{3/4}}{log N})$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=666666;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
ll n,w[maxn],g[maxn];
int sq,pri[maxn],pl,tot,id1[maxn],id2[maxn];
bool vis[maxn];
inline int id(ll x){return x<=sq?id1[x]:id2[n/x];}
void init(){
    sq=sqrt(n);
    FOR(i,2,sq){
        if(!vis[i]) pri[++pl]=i;
        FOR(j,1,pl){
            if(i*pri[j]>sq) break;
            vis[i*pri[j]]=true;
            if(i%pri[j]==0) break;
        }
    }
    for(ll l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        w[++tot]=n/l;
        if(n/l<=sq) id1[n/l]=tot;
        else id2[n/(n/l)]=tot;
        g[tot]=w[tot]-1;
    }
}
void calc(){
    FOR(i,1,pl) FOR(j,1,tot){
        if((ll)pri[i]*pri[i]>w[j]) break;
        g[j]-=g[id(w[j]/pri[i])]-(i-1);
    }
}
int main(){
    scanf("%lld",&n);
    init();
    calc();
    printf("%lld
",g[id(n)]);
}