题解 P2291 【[PA2011]Prime prime power 质数的质数次方】

· · 题解

求第 k 小的 a^b>n，a,b\in Prime。

这种东西一看就不是很好做，但是我们考虑 2^{67} 远远大于 10^{18}，所以可以确认 b 最大不会超过 67，且 b 是质数，那么 b\in\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61\}。

幂次这么少，是不是直接枚举就可以呢？但我们发现 b=2 时比较特殊，a\leq 10^9，而 b\geq 3 时 a\leq 10^6，对于 a\leq 10^9 这个范围我们是不能承受的。所以考虑根据 n 的范围得出 b=2 时的一个紧确上下界。由 n>a^2 得到 \sqrt n> a，并且根据 k\leq 100000，我们大概推算出 a\in(\sqrt n,\sqrt n+3\times 10^6]\bigcap \mathrm{Prime}。这样我们筛出 a\in(\sqrt n,\sqrt n+3\times 10^6] 内的质数，并统计贡献就解决了 b=2 时的情况。

对于 b\geq 3 的情况，设每个 b 对应的 a 的上界都为 10^6，则最多枚举了 \frac{10^6}{\ln 10^6}\times 17\approx 1214185 个数。事实上远远达不到该上界，因为 a^b 会快速增长直到远远大于 10^{18}。

在实际情况下，我们会发现上述理论估算存在误差，对于 b\geq 3 的情况 a 的上界大概在 2\times 10^6 处才能取到所有答案，需要微调。

本代码可以通过 \text{darkbzoj} 所有数据，\text{Luogu} 数据太水了/fad

#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
//18*78498=1412964
typedef unsigned long long ll;
int num=0,tot=0;
const int sp[]={3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};
int p[4000005],v[4000005];
ll n,ans[10000005];
inline ll read() {
    ll x=0,f=1;register char s=getchar();
    while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
    return x*f;
}
inline void write(ll x) {
    if(x==0) {return;}
    write(x/10);
    putchar((char)('0'+x%10));
}
inline ll pow(ll x,ll p) {ll res=1;for(;p;p>>=1) {if(p&1) res=res*x; x=x*x;} return res;}
inline void makePrime(int n) {
    for(register int i=2;i<=n;++i) {
        if(!v[i]) p[++num]=i;
        for(register int j=1;j<=num&&i*(ll)p[j]<=n;++j) {
            v[i*p[j]]=1;
            if(i%p[j]==0) break;
        }   
    }
} 
inline void makePrime(int l,int r) {
    for(register int i=0;i<=r-l;++i) v[i]=0;
    if(l==1) v[0]=1;
    for(register int i=1;i<=num;++i) {
        int x=p[i];
        for(register int j=r/x*x;j>=l&&j>x;j-=x) {v[j-l]=1;}
    }
    for(register int i=l;i<=r;++i) {
        if(!v[i-l]&&i*(ll)i!=n) ans[++tot]=i*(ll)i;
    }
}
inline void divide(ll n) {
    for(ll i=2;i<=n;++i) {
        if(n%i) continue;
        int cnt=0;
        while(n%i==0) {n/=i; ++cnt;}
        printf("%lld %d\n",i,cnt);
    }
}
signed main() {
    n=read(); int k=read();
    makePrime(4e6);
    makePrime((int)ceil(sqrt(n)),(int)ceil(sqrt(n))+(int)3e6);
    for(register int i=1;i<=num&&p[i]<=2e6;++i) {
        for(register int j=0;j<17;++j) {
            ll tmp=0;
            if((sp[j]*log(p[i]))>=log((double)ULLONG_MAX)) break;
            if((tmp=pow((ll)p[i],(ll)sp[j]))>n) ans[++tot]=tmp;
        }
    }
    std::sort(ans+1,ans+1+tot);
    printf("%llu\n",ans[k]);
    return 0;
}