专栏文章

P2291 Prime prime power

NNoirCube1
P2291题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq41qlx
此快照首次捕获于
2025/12/03 22:36
3 个月前
此快照最后确认于
2025/12/03 22:36
3 个月前
查看原文
观察：b≤61{b\leq 61}。
鉴于 bb 很少，所以也许我们可以枚举所有的 (a,b)(a,b)。
对于 b≥3b\ge 3，我们可以直接暴力，但是唯一的问题就是 b=2b=2 的时候 a≤109a\leq 10^9。
发现尽管 nn 大得恐怖，但是 k≤105k\leq 10^5。在此基础上，只有很少一部分平方数会影响答案，于是我们暴力枚举 10410^4 个平方数，检验它们是不是质数的平方就行了。
因为你可能要把所有 b≥3b \ge 3 的合法数放进一个 set 当中，所以会导致复杂度多一个 log⁡n\log n。
CPP
#define int long long
signed main() {
	int n, k;
	cin >> n >> k;
	int bnd = ceil(sqrt(n));
	init(6e6);
	for (int i = 1; i <= tot; i++) {
		int now = 1;
		for (int j = 1; ; j++) {
			now *= primes[i];
			if (p[j] == 0 && now > n) s.insert(now);
			if (primes[i] > 1e18 / now) break;
		}
	}
	for (int i = 1; i <= 10000; i++) {
		if (bnd + i - 1 > 1e9) break;
		if (pr(bnd + i - 1)) s.insert((bnd + i - 1) * (bnd + i - 1));
	}
	for (int i = 1; i < k; i++) s.erase(s.begin());
	cout << *s.begin() << endl;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...