P2291 Prime prime power

NoirCube1 · 2025-02-28 21:27:05 · 题解

观察：{b\leq 61}。

鉴于 b 很少，所以也许我们可以枚举所有的 (a,b)。

对于 b\ge 3，我们可以直接暴力，但是唯一的问题就是 b=2 的时候 a\leq 10^9。

发现尽管 n 大得恐怖，但是 k\leq 10^5。在此基础上，只有很少一部分平方数会影响答案，于是我们暴力枚举 10^4 个平方数，检验它们是不是质数的平方就行了。

因为你可能要把所有 b \ge 3 的合法数放进一个 set 当中，所以会导致复杂度多一个 \log n。

#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;
}