BZOJ3070 : [Pa2011]Prime prime power 质数的质数次方

时间：2021-01-15 11:02:32

对于$a^b$，如果$b=2$，那么在$[\sqrt{n},\sqrt{n}+k\log k]$内必定能找到$k$个质数作为$a$。

筛出$n^{\frac{1}{4}}$内的所有质数，暴力枚举所有落在该区间内的倍数，将其筛掉，即可判断每个数是否是质数。

然后以最大的质数的平方作为上界，枚举更大的$a$和$b$，这里方案数指数级下降，故暴力即可。

最后排序输出第$k$小的值即可。

时间复杂度$O(n^{\frac{1}{3}}+k\log^2k)$。

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long ll;

const int N=1050010;

ll n,lim,t,o,b[66],q[N*2];int cnt,k,m,i,j,a[66],p[N],tot;bool v[N],vis[N*2];

inline ll pow(ll a,int b){

  ll t=1;

  while(b--){

    if(a>lim/t)return lim+1;

    t*=a;

  }

  return t;

}

inline ll powfast(ll a,int b){ll t=1;for(;b;b>>=1,a*=a)if(b&1)t*=a;return t;}

void sieve(ll n){

  int i,j;

  for(tot=0,i=2;i<=n;i++){

    if(!v[i])p[tot++]=i;

    for(j=0;j<tot&&i*p[j]<=n;j++){

      v[i*p[j]]=1;

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

    }

  }

}

inline void check(int x){for(ll i=max(t/x*x,2LL*x);i<=lim;i+=x)if(i>=t)vis[i-t]=1;}

int main(){

  scanf("%lld%d",&n,&k);

  t=max((ll)sqrt(n)-10,2LL);

  while(t*t<=n)t++;

  sieve((ll)sqrt(lim=t+max(k,10)*21)+5);

  for(i=0;i<tot;i++)check(p[i]);

  for(o=t;o<=lim&&cnt<k;o++)if(!vis[o-t])q[++cnt]=o*o;

  lim=q[cnt];

  for(i=3;;a[++m]=i++)if((1LL<<i)>lim)break;

  for(b[1]=2;(b[1]+1)*(b[1]+1)*(b[1]+1)<=lim;b[1]++);

  for(i=2;i<=m;i++)for(b[i]=b[i-1];pow(b[i],a[i])>lim;b[i]--);

  sieve(max(b[1],1LL*a[m]));

  for(i=1;i<=m;i++)if(!v[a[i]]){

    for(j=0;j<tot&&powfast(p[j],a[i])<=n;j++);

    for(;j<tot&&p[j]<=b[i];j++)q[++cnt]=powfast(p[j],a[i]);

  }

  sort(q+1,q+cnt+1);

  return printf("%lld",q[k]),0;

}

　　

相关文章