B. T-primes 题解喵~

哈喽呀，各位同学！本喵今天给大家带来 Codeforces 230B 题的详细解析哦。这道题看起来有点吓人，数字那么大，但其实只要找到其中的小秘密，就会发现它是一只很温顺的“小猫咪”啦，喵~

---

题目大意

首先，我们来理解一下题目的要求吧！

题目定义了一种新的数，叫做 T-素数 (T-prime)。一个正整数如果恰好有三个不同的正整数因子，那么它就是 T-素数。

现在呢，会给你 n 个正整数，你需要判断它们中的每一个数是不是 T-素数。

举个例子：

• 数字 4 的因子有 1, 2, 4，正好三个，所以 4 是一个 T-素数。
• 数字 5 的因子有 1, 5，只有两个，所以它不是 T-素数（它是普通的素数啦）。
• 数字 6 的因子有 1, 2, 3, 6，有四个，所以它也不是 T-素数。

输入数字的范围很大哦，最大可以到 10^12，所以我们的算法可不能太暴力呀！

---

解题思路

那么，到底什么样的数才会有恰好三个因子呢？让本喵来带你分析一下喵~

我们知道，任何大于 1 的整数 t，都至少有两个因子：1 和它本身 t。 要想恰好有三个因子，就意味着除了 1 和 t 之外，必须有且仅有一个因子。我们把这个因子叫做 p 好了。

所以，一个 T-素数的因子集合必须是 {1, p, t}。

根据因子的性质，如果 p 是 t 的因子，那么 t/p 也必须是 t 的因子。 因为我们只有三个因子，所以 t/p 只能是 1, p, t 中的一个。

• t/p 不可能是 1，因为那样 p 就等于 t 了，和我们假设的 p 是中间那个因子矛盾了。
• t/p 也不可能是 t，因为那样 p 就等于 1 了，也矛盾了。

所以，只剩下一种可能啦：t/p = p！ 也就是说 t = p * p。

这说明，一个 T-素数必须是一个完全平方数！

那是不是所有完全平方数都是 T-素数呢？比如 36 = 6*6，它的因子有 1, 2, 3, 4, 6, 9, 12, 18, 36，远不止三个。 所以，我们对 p 还有要求。

让我们再想想 t = p*p 的因子。

• 如果 p 是一个素数，比如 p=2，那么 t = 4。4 的因子就是 1, 2, 4，正好三个！
• 如果 p 是一个合数，比如 p=6，6 的因子是 1, 2, 3, 6。那么 t = 36 的因子除了 1, 6, 36 之外，p 的因子（比如 2 和 3）也都会成为 t 的因子，这样一来因子数量就超过三个了。

所以，结论就出来啦，喵！ 一个数是 T-素数，当且仅当它是某个素数的平方。

有了这个超级棒的结论，我们的解题步骤就清晰了：

1. 对于给定的数字 x，我们先判断它是不是一个完全平方数。
2. 如果是，我们求出它的平方根 r = sqrt(x)。
3. 然后，我们再判断这个平方根 r 是不是一个素数。
4. 如果 x 是完全平方数 并且 它的平方根 r 是素数，那么 x 就是 T-素数！否则就不是。

考虑到输入的 x 最大是 10^12，它的平方根 r 最大就是 10^6。我们需要判断很多次一个数是不是 10^6 以内的素数。如果每次都用试除法去判断，肯定会超时。

所以，最好的办法就是预处理！我们可以用埃拉托斯特尼筛法（Sieve of Eratosthenes），先把 1 到 10^6 范围内的所有素数都找出来，存到一个布尔数组里。这样，后面每次判断一个数是不是素数，只需要 O(1) 的时间复杂度查询一下数组就好啦！

总结一下最终的算法：

1. 预处理：使用埃氏筛法，标记出 1 到 10^6 中所有的素数。
2. 处理查询：对输入的 n 个数，逐个进行以下判断： a. 计算 x 的平方根 r。 b. 检查 x 是否真的是 r 的平方（r * r == x）。 c. 如果是，并且 r 在我们预处理的素数表里被标记为素数，就输出 "YES"。 d. 其他所有情况，都输出 "NO"。

这样就完美解决问题啦，喵~

---

代码实现

这是本喵为各位同学准备的 C++ 代码，加了一些注释方便理解哦！

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

// x 的最大值是 10^12，所以它的平方根最大是 10^6。
// 我们需要一个筛子来处理到 10^6 的范围，喵~
const int SIEVE_LIMIT = 1000000;

// 一个布尔向量来存某个数是不是素数。is_prime[i] 为 true 就代表 i 是素数。
// std::vector<bool> 是一个空间优化过的 vector，专门存 bool 值的，很省空间哦！
std::vector<bool> is_prime(SIEVE_LIMIT + 1);

// 埃拉托斯特尼筛法，用来预处理素数
void sieve() {
    // 一开始，我们乐观地认为所有数字都是素数，喵~
    std::fill(is_prime.begin(), is_prime.end(), true);
    
    // 但是 0 和 1 不是素数，这是常识啦！
    is_prime[0] = is_prime[1] = false;

    // 从 2 开始遍历到筛法范围的平方根
    for (int p = 2; p * p <= SIEVE_LIMIT; ++p) {
        // 如果 p 还是一个素数（没被前面的数筛掉）
        if (is_prime[p]) {
            // 那就把 p 的所有倍数都标记为非素数
            // 我们可以从 p*p 开始，因为比它小的倍数肯定已经被更小的素数筛掉了
            for (int i = p * p; i <= SIEVE_LIMIT; i += p) {
                is_prime[i] = false;
            }
        }
    }
}

int main() {
    // 用这个可以让 cin 和 cout 跑得飞快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 在处理查询之前，先把素数筛好！
    sieve();

    int n;
    std::cin >> n;

    for (int i = 0; i < n; ++i) {
        long long x;
        std::cin >> x;

        // T-素数是素数的平方，最小的 T-素数是 4 (2*2)。
        // 所以小于 4 的数肯定不是 T-素数。
        if (x < 4) {
            std::cout << "NO\n";
            continue;
        }

        // 计算整数平方根。用 long double 的 sqrtl 会更精确一些。
        long long root = round(sqrtl(x));

        // 检查 x 是不是一个完全平方数，以及它的根是不是素数
        if (root * root == x) {
            // 因为 x <= 10^12，所以 root <= 10^6，正好在我们的筛法范围内。
            if (is_prime[root]) {
                std::cout << "YES\n";
            } else {
                std::cout << "NO\n";
            }
        } else {
            std::cout << "NO\n";
        }
    }

    return 0;
}

---

知识点小课堂

什么是 T-素数呀？

从数学上讲，一个正整数 N 的正因子个数可以用因子函数 τ(N) (tau) 来表示。 如果 N 的标准素数分解是 N = p₁^a₁ * p₂^a₂ * ... * pₖ^aₖ，其中 pᵢ 是不同的素数，aᵢ 是对应的指数。 那么因子个数就是 τ(N) = (a₁ + 1) * (a₂ + 1) * ... * (aₖ + 1)。

题目要求因子个数恰好为 3，也就是 τ(N) = 3。 因为 3 是一个素数，所以上面的乘积公式中，只能有一项，并且这一项必须等于 3。 也就是说，k=1 并且 a₁ + 1 = 3。 解出来就是 a₁ = 2。 所以，N 的形式必须是 p₁²，其中 p₁ 是一个素数。

这就是“T-素数必须是素数的平方”的严格证明啦，是不是很简单呀？

什么是埃氏筛法呀？

埃拉托斯特尼筛法（Sieve of Eratosthenes），简称埃氏筛，是一种古老而高效的寻找一定范围内所有素数的方法。它的思想就像筛豆子一样，把不是素数的“合数”都筛掉，剩下的就是素数啦！

步骤如下：

1. 创建一个列表，包含从 2 到你想要的上限 N 的所有整数。初始时，假设它们都是素数。
2. 从第一个素数 p = 2 开始。
3. 将 p 的所有倍数（2p, 3p, 4p, ...）从列表中标记为合数（非素数）。
4. 找到下一个没有被标记的数，这个数就是下一个素数（这里是 3）。
5. 重复步骤 3 和 4，用新的素数（3）去标记它的所有倍数。
6. 一直重复这个过程，直到你检查完所有小于等于 sqrt(N) 的素数。

当筛法结束后，列表中所有未被标记的数就都是素数啦！这个方法非常高效，预处理 10^6 以内的素数只需要一瞬间，喵~

希望这篇题解能帮助到你！如果还有不懂的地方，可以随时再来问本喵哦！下次见啦！