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

容易发现，$2^{67}=147573952589676412928$ 远远大于 $10^{18}$ ，不可能是答案。因此我们只需要考虑 $2$ 到 $61$ 次方产生的贡献。 又容易发现， $\sqrt[3]{10^{18}}=10^6$ 。 在 $10^{6}$ 到 $2\times10^{6}$ 中间大约有质数 $1.37\times 10^5$ 个，因此对于指数大于等于 $3$ 的部分底数不会超过 $2\times 10^6$ 。 这部分利用线性筛即可处理完毕。 麻烦的是指数为 $2$ 的部分， 因为这部分底数都是 $10^9$ 级的。 不过，通过估算我们可以发现在 $10^9$ 到 $10^9+10^6$ 之间一共有质数 $4.7\times 10^5$ 个，因此我们的底数不会超过 $10^9+10^6$ 。这样的话底数的跨度不会超过 $10^6$， 我们完全可以一个个枚举观察是否是质数。 至于快速判断一个数是不是质数，那当然是 $millerrabin$ 算法了。单次计算时间复杂度 $O(\log w)$ 。 我们把每个不同指数当前大于 $n$ 的最小数字放到堆里面，每次取出最小的后更新一下就可以了。 时间复杂度 $O(10^6\log 10^9+k\log 18)$ 。 代码: ```cpp #include<bits/stdc++.h> #include<cctype> #define For(i,a,b) for(i=(a),i##end=(b);i<=i##end;++i) #define Forward(i,a,b) for(i=(a),i##end=(b);i>=i##end;--i) #define Rep(i,a,b) for(register uint32 i=(a),i##end=(b);i<=i##end;++i) #define Repe(i,a,b) for(register uint32 i=(a),i##end=(b);i>=i##end;--i) #define Chkmax(a,b) a=a>b?a:b using namespace std; template<typename T>inline void read(T &x){ T s=0,f=1;char k=getchar(); while(!isdigit(k)&&k^'-')k=getchar(); if(!isdigit(k)){f=-1;k=getchar();} while(isdigit(k)){s=s*10+(k^48);k=getchar();} x=s*f; } void file(void){ #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); #endif } using uint64=unsigned long long; using uint128=__uint128_t; using uint32=unsigned int; const uint32 bace[5]={2,3,7,61,24251}; inline uint32 pow(uint32 x,uint32 y,uint32 mod) { static uint32 sm; for(sm=1;y;y>>=1,x=(uint64)x*x%mod)if(y&1)sm=(uint64)sm*x%mod; return sm; } inline bool millerrabin(uint32 x) { if(x<2)return false; if(x==2||x==3||x==7||x==61||x==24251)return true; static uint32 ba,r;ba=x-1; static uint32 ti,j;ti=0; while(!(ba&1))ba>>=1,++ti; Rep(i,0,4) { r=pow(bace[i],ba,x); if(r==1||r==x-1)continue; for(j=1;j<=ti;++j) { r=(uint64)r*r%x; if(r==x-1)break; } if(j>ti)return false; } return true; } static uint64 n; static uint32 k; static struct nd { uint32 nm, pw; uint64 w; friend bool operator < (nd a, nd b) {return a.w > b.w;} }z; priority_queue <nd> Q; const int MAXN = 2e5 + 7; static uint32 pri[MAXN], e; bitset <2000001> is; inline void getpri() { const int lm = 2e6; Rep(i, 2, lm) { if(!is.test(i)) pri[++ e] = i; for(register int j = 1; j <= e && i <= lm / pri[j]; ++ j) { is.set(i * pri[j]); if(i % pri[j] == 0) break; } } } inline uint64 power(uint32 u, uint32 v) { uint64 d = 1; while(v --) { if(d > LLONG_MAX / u) return LLONG_MAX; d *= u; } return d; } int main() { file(); read(n); getpri(); Rep(i, 2, 18) { z = (nd){1, pri[i], 1llu << pri[i]}; while(z.w <= n) { ++ z.nm; z.w = power(pri[z.nm], z.pw); } Q.push(z); } uint32 r = sqrt(n); while((uint64) r * r <= n) ++ r; if(r % 2 == 0) ++ r; while(! millerrabin(r)) r += 2; Q.push((nd){r, 2, (uint64) r * r}); read(k); while(-- k) { z = Q.top(), Q.pop(); if(z.pw == 2) { z.nm += 2; while(! millerrabin(z.nm)) z.nm += 2; Q.push((nd){z.nm, 2, (uint64) z.nm * z.nm}); } else Q.push((nd){z.nm + 1, z.pw, power(pri[z.nm + 1], z.pw)}); } printf("%llu\n", Q.top().w); cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl; return 0; } ```