题目大意

给定一个整数 $n$（$2 \le n \le 10^9$），判断是否能找到三个不同的整数 $a, b, c$，满足 $2 \le a, b, c$ 且 $a \cdot b \cdot c = n$。若存在，输出任意一组；否则输出 "NO"。

解题思路

假设我们按升序排列 $a < b < c$。
为了尽可能让 $a$ 小，我们首先寻找 $n$ 的最小因子（大于 $1$），记为 $a$。
然后，在去掉 $a$ 之后，剩余部分为 $n / a$。接下来，我们寻找 $n / a$ 的最小因子，且该因子不能等于 $a$ 也不能是 $1$，记为 $b$。
最后，令 $c = n / (a \cdot b)$。
如果 $c$ 也满足 $c \ge 2$ 且 $c \neq a$ 且 $c \neq b$（由构造过程自动满足 $c > b$ 因为 $b$ 是 $n/a$ 的最小非 $1$ 非 $a$ 的因子），则得到一组解；否则无解。

算法步骤

1. 对每个测试用例的 $n$：
   • 寻找 $n$ 的最小真因子 $a$（$a \ge 2$）。若 $n$ 是质数，则不存在这样的 $a$，直接输出 "NO"。
   • 令 $m = n / a$。
   • 寻找 $m$ 的最小因子 $b$，满足 $b \ge 2$ 且 $b \neq a$。若不存在这样的 $b$，则输出 "NO"。
   • 令 $c = m / b$。检查 $c$ 是否满足 $c \ge 2$ 且 $c \neq a$ 且 $c \neq b$。若满足，则输出 "YES" 和 $a, b, c$；否则输出 "NO"。

正确性说明

• 由于 $a$ 是 $n$ 的最小因子（$>1$），任何其他因子都 $\ge a$。
• 同理，$b$ 是 $m$ 的最小因子且不等于 $a$，保证了 $b \ge a$ 且 $b \neq a$，因此 $b > a$。
• 最后 $c = m / b$，因为 $b$ 是 $m$ 的最小非 $1$ 非 $a$ 的因子，所以 $c \ge b$，并且若 $c = b$ 则意味着 $m = b^2$，此时 $b$ 是唯一因子，但我们已经要求 $b \neq a$，且 $a \neq b$，所以 $c$ 不可能等于 $b$ 或 $a$（除非 $a = b = c$，但此时 $n = a^3$，且 $a$ 是 $n$ 的最小因子，则 $n = a^3$ 时 $a$ 是最小因子，那么 $m = a^2$，最小因子 $b$ 可能等于 $a$，但被排除，因此若 $a^2$ 没有其他因子则无解，这符合逻辑）。因此 $c > b$ 自动满足。
• 若这样的 $a, b, c$ 存在，它们必然互不相同且 $\ge 2$，即为合法解。

时间复杂度

寻找一个数的因子需要 $O(\sqrt{n})$ 的试除。对于每个测试用例，我们最多进行两次这样的查找（一次找 $a$，一次找 $b$），因此总复杂度 $O(t \cdot \sqrt{n})$，在 $t \le 100$ 且 $n \le 10^9$ 时足够快。

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        // 寻找 a：n 的最小因子（>1）
        int a = -1;
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                a = i;
                break;
            }
        }
        if (a == -1) { // n 是质数
            cout << "NO\n";
            continue;
        }

        int m = n / a;

        // 寻找 b：m 的最小因子（>1 且不等于 a）
        int b = -1;
        for (int i = 2; i * i <= m; ++i) {
            if (m % i == 0 && i != a) {
                b = i;
                break;
            }
        }
        // 注意：b 可能来自 i 或 m/i，需要检查两个方向
        if (b == -1) {
            // 检查 m 本身是否满足（即 b = m 的情况，但要保证 m != a 且 m >= 2）
            if (m != a && m >= 2) {
                b = m;
            }
        }
        if (b == -1 || b == a) {
            cout << "NO\n";
            continue;
        }

        int c = m / b;
        if (c >= 2 && c != a && c != b) {
            cout << "YES\n" << a << " " << b << " " << c << "\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

示例解析

以 $n = 64$ 为例：

• 最小因子 $a = 2$，$m = 32$。
• $m$ 的最小因子（$\neq a$）为 $b = 4$（因为 $2$ 已被占用），$c = 32 / 4 = 8$。
  $a=2, b=4, c=8$ 均 $\ge 2$ 且互不相同，乘积为 $64$，输出 "YES 2 4 8"。

以 $n = 32$ 为例：

• $a = 2$，$m = 16$。
• $m$ 的最小因子（$\neq a$）为 $b = 4$（注意 $2$ 不行），$c = 16 / 4 = 4$。但 $c = b$，不满足互异，故无解。

以 $n = 97$ 为例：质数，直接输出 "NO"。

总结

本题的关键是贪心地取最小可能的 $a$ 和 $b$，然后检查剩余的 $c$ 是否合法。这种方法避免了枚举所有因子组合，保证了 $O(\sqrt{n})$ 的效率。