新闻详情

[PA 2011] Prime prime power 质数的质数次方

事实上只需要会求最小的一个 \(>n\) 的 \(a^b\) 即可。
对于 \(b>2\) 的情况，\(a\) 一定不会超过 \(3\times 10^6\)（基于调参，就是比 \(\sqrt[3]{10^{18}}=10^6\) 略大），所以暴力把 \(\leq 3\times 10^6\) 的每个质数的每个质数次方塞进一个 set 里。

对于 \(b=2\) 的情况，\(a^2 >n\) 且不会大太多的质数并不会太多，通过调参可得只需要选 \(>\sqrt{n}\) 的前 \(3 \times 10^6\) 个数中的质数（质数个数约为 \(\frac{3\times 10^6}{\ln 3 \times 10^6}\approx 2\times 10^5>k\) 个）即可。令 \(M=3\times 10^6\)，用埃氏筛能以 \(O(M\log \log M)\) 的复杂度筛出这些质数，把他们的平方放进 set 里。

然后 set 执行 \(k\) 次 upper_bound 操作即可。

点击查看代码

#include <bits/stdc++.h>
#define ll long long
using namespace std; 
const int MAXN=1e7+50;
int prime[MAXN];
bool st[MAXN];
int tot;
set<ll>S;
ll Next(ll x)
{return *S.upper_bound(x);
}
ll N;
int K;
bool vis[MAXN];
int main()
{int MAX=6000000;st[1]=true;for(int i=2;i<=MAX;i++){if(st[i]==false){prime[++tot]=i;}for(int j=1;i*prime[j]<=MAX;j++){st[i*prime[j]]=true;if(i%prime[j]==0)break;}}for(int i=1;i<=tot;i++){int Cnt=1;ll Now=prime[i];while((__int128)Now*prime[i]<=8e18){Now*=prime[i];Cnt++;if(st[Cnt]==false){S.insert(Now);}}}cin>>N>>K;ll Sq=ceil(sqrt(N));ll l=Sq,r=Sq+3000000;for(int i=1;1ll*prime[i]*prime[i]<=Sq+3000000;i++){	for(ll j=((l-1)/prime[i]+1)*prime[i];j<=r;j+=prime[i]){vis[j-l]=true;}}for(int i=0;i<=3000000;i++){if(vis[i]==false){S.insert(1ll*(i+l)*(i+l));}}	ll Now=N;while(K--){Now=Next(Now);}cout<<Now;
}