自动搬运

查看原文

来自洛谷，原作者为

	tommymio Cruel world

搬运于2025-08-24 21:36:00，当前版本为作者最后更新于2020-11-28 22:10:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

求第 $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;
}