[LOJ6235]区间素数个数

题目大意：
　　给定$n(n\leq10^{11})$，求$\pi(n)$。

思路：
　　计算$\pi$函数有$O(n^{\frac23})$的Lehmer算法，这里考虑$O(\frac{n^{\frac34}}{\ln n})$的洲阁筛。
　　我们可以将答案分为$\leq\sqrt n$的质数个数和$>\sqrt n$的质数个数。
　　其中$\leq\sqrt n$的质数个数可以线性筛预处理，而$>\sqrt n$的质数个数相当于用$\leq\sqrt n$的质数筛这$n$个数后剩下的数的个数。
　　若用$f[i][j]$表示$1\sim j$中与前$i$个数互质的数的个数，则转移方程为$f[i][j]=f[i-1][j]-f[i-1][\lfloor\frac j{p_i}\rfloor]$。$\pi(n)\sim\frac n{\ln n}$，$j$有$\sqrt n$种取值，时间复杂度$O\left(\frac n{\ln\sqrt n}\right)=O\left(\frac n{\ln n}\right)$。
　　当$p_{i+1}>j$时，$f[i][j]=1$。所以当$p_i>\frac j{p_i}$时，转移方程变为$f[i][j]=f[i-1][j]-1$。
　　因此对于每一个$j$，只需计算$p_i^2\leq j$的$f[i][j]$即可。对于$p_i^2>j$的$j$，可以记录最后一步的$i$是多少，转移的时候把那些$1$一起减掉。答案就是一开始线性筛求出的$\leq\sqrt n$的质数个数+用$\leq\sqrt n$筛完剩下的数。注意筛完除了那些$>\sqrt n$的质数，还会剩下$1$，因此最后要把$1$去掉。
　　时间复杂度$O\left(\frac{n^\frac34}{\ln n}\right)$。

 #include<cmath>

 #include<cstdio>

 #include<cctype>

 #include<algorithm>

 typedef long long int64;

 inline int64 getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int64 x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int LIM=,P=;

 bool vis[LIM];

 int lim,p[P],sum[LIM],last[LIM*],cnt;

 int64 val[LIM*],f[LIM*];

 inline void sieve() {

     for(register int i=;i<=lim;i++) {

         if(!vis[i]) p[++p[]]=i;

         sum[i]=sum[i-]+!vis[i];

         for(register int j=;j<=p[]&&i*p[j]<=lim;j++) {

             vis[i*p[j]]=true;

             if(i%p[j]==) break;

         }

     }

 }

 int main() {

     const int64 n=getint();

     lim=sqrt(n);

     sieve();

     for(register int64 i=;i<=n;i=n/(n/i)+) {

         val[++cnt]=n/i;

     }

     std::reverse(&val[],&val[cnt]+);

     std::copy(&val[],&val[cnt]+,&f[]);

     for(register int i=;i<=p[];i++) {

         for(register int j=cnt;j;j--) {

             const int64 k=val[j]/p[i],pos=k<=lim?k:cnt+-n/k;

             if(k<p[i]) break;

             f[j]-=f[pos]+last[pos]-i+;

             last[j]=i;

         }

     }

     printf("%lld\n",sum[lim]+f[cnt]-);

     return ;

 }