[CF665F]Four Divisors

题目大意：
　　给定$n(n\leq10^{11})$，求$\displaystyle\sum_{i=1}^n[\tau(i)=4]$。

思路：
　　设$p,q$为不相等的质数，则满足$\tau(i)=4$的数$i$一定可以表示成$pq$或$p^3$。
　　对于$i=pq$的情况，可以先线性筛预处理出$\sqrt n$以内的质数，然后用LOJ6235的方法，用洲阁筛求出DP数组$f$。加上$last[j]-1$就是当$p_i^2>j$时不用$-1$转移，也就是加上了$p_i^2>j$的质数个数。此时$f[cnt+1-p_i]$表示的就是$\pi(n/p_i)-\pi(\sqrt n)$。统计答案时，枚举素数$p_i$，求$\sum_{p_i\leq\sqrt n}(\pi(n/p_i)-\pi(p_i))$即可。
　　对于$i=p^3$的情况，直接在筛出来的质数中二分答案即可。
　　时间复杂度$O\left(\frac{n^{\frac34}}{\ln n}\right)$。

细节：
　　$n=1$时二分会挂掉，需要特判。

 #include<cmath>

 #include<cstdio>

 #include<cctype>

 #include<algorithm>

 #include<functional>

 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 n,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() {

     lim=sqrt(n=getint());

     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;

         }

     }

     int64 ans=;

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

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

     }

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

         ans+=f[cnt+-p[i]]-i;

     }

     if(n!=) ans+=std::upper_bound(&p[],&p[p[]]+,floor(pow(n,./)))-&p[];

     printf("%lld\n",ans);

     return ;

 }

巴特西

[CF665F]Four Divisors

最新文章

热门文章