官方题解｜美丽数 II

题目解析

本题若我们直接使用质因数分解，对于 $A_i$ 执行普通的质因数分解，时间复杂度为 $\mathrm{O}(\lfloor\sqrt{A_i}\rfloor)$，对于 $N$ 个查询，总的时间复杂度为 $\mathrm{O}(N\lfloor\sqrt{\max(A_i)}\rfloor)$；然而这个计算量达到了 $10^4 \times 10^5 = 10^9$ 级别，无法在时限内通过题目。

根据 素数定理：

$$\pi(x) \approx \frac{x}{\ln{x}}$$

其中 $\pi(x)$ 表示：不超过 $x$ 的整数中素数的数量。

实际上 $10^5$ 以内的素数只有 $9592$ 个。

所以我们可以把 $10^5$ 内所有的 $9592$ 个素数预处理，来加速质因数分解，使其复杂度降为 $\mathrm{O}(\pi(\lfloor\sqrt{\max(A_i)}\rfloor)$。这样整个算法时间复杂度为 $\mathrm{O}\left(N \times \pi(\lfloor\sqrt{\max(A_i)}\rfloor)\right)$；其计算量大约为 $10^4 \times 10^4 = 10^8$，可以在时限内通过题目。

AC代码

#include <bits/stdc++.h>
 
using i64 = long long;

constexpr int N = 1e5;

std::bitset<N + 1> st;
std::vector<int> primes;

auto sieve = []() {
    for (i64 i = 2; i <= N; ++i) {
        if (st[i]) continue;
        for (i64 j = i * i; j <= N; j += i)
            st[j] = 1;
        primes.push_back(i);
    }
    return 0;
} ();

int solve() {
    i64 n; std::cin >> n;
    int cnt = 0;
    for (auto &p: primes) {
        while (n % p == 0) {
            n /= p;
            cnt += 1;
        }
        if (cnt > 3) break;
    }
    if (n > 1) cnt += 1;
    std::cout << (cnt == 3 ? "Yes" : "No") << '\n';
    return 0;   
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int _; std::cin >> _;
    while (_--) solve();
    return 0;
}