Moe's CF Life

喵~ 主人好呀！今天由我，你的专属小猫娘，来带你解决一道关于数字分解的题目，感觉会很有趣呢，嘻嘻~ 这道题叫做 "Product of Three Numbers"，我们要像小猫咪寻宝一样，从一个大数字里找出三个小小的、不同的因子！

题目大意

题目要求是这样的喵：给你一个整数 n，你需要找到三个不同的整数 a, b, c，它们都得大于等于 2，并且它们的乘积正好等于 n (a * b * c = n)。

如果能找到，就开心地喊出 "YES"，然后把 a, b, c 这三个数字告诉大家。如果找不到，就只好遗憾地说 "NO" 啦。我们要处理好多组这样的询问哦~

举个例子：

如果 n = 64，我们可以找到 2 * 4 * 8 = 64。这三个数 2, 4, 8 都是大于等于2且互不相同的，所以是可行的解！
如果 n = 32，我们可能找到 2 * 4 * 4。哎呀，有两个 4，重复了，不行！或者 2 * 2 * 8，也有重复的 2。所以对于 32 来说，找不到三个不同的数，答案就是 "NO"。

题解方法

看到这道题，我的猫猫直觉告诉我，这一定和找因数有关，对吧？既然要找三个数，那我们一个一个来找不就好了嘛，就像小猫咪一步一步悄悄接近猎物一样，哼哼~

我们可以用一种贪心（Greedy）的策略哦。什么是贪心呢？就是每一步都做出当前看起来最好的选择！在这里，“最好”的选择就是找最小的因数。为什么呢？因为我们先把最小的因数 a 和 b 拿走，剩下的那个数 c 就会尽可能地大，这样 c 不仅更容易满足 c >= 2 的条件，也更不容易和 a、b 重复，找到解的概率就更高啦，喵~

所以，我们的步骤是这样的：

寻找第一个因数 a：我们来找 n 的最小因数 a。我们就从 2 开始，一个一个试，第一个能整除 n 的数就是 a 啦。为了快一点，我们只需要试到 sqrt(n) 就可以了哦。如果找不到，说明 n 是个质数，不可能分解成三个数的乘积，直接说 "NO"。
寻找第二个因数 b：找到 a 之后，我们把它从 n 里面“除掉”，得到一个新的数 n' = n / a。接下来，我们在 n' 中找它的最小因数 b。但是要记住，a, b, c 必须是不同的！所以 b 不能等于 a。为了保证这一点，我们可以从 a + 1 开始寻找 b。同样，我们只需要试到 sqrt(n')。如果找不到，那也只好放弃了。
确定第三个数 c：找到 b 之后，我们再把它从 n' 中“除掉”，剩下的数就是 c = n' / b。
最终检查：最后一步，也是最关键的一步！我们要检查一下这个 c 是不是一个合格的“小伙伴”。它需要满足三个条件：
- c 要大于 1（也就是 c >= 2）。
- c 不能等于 a。
- c 也不能等于 b。
输出结果：如果这三个条件都满足，那恭喜主人，我们成功啦！输出 "YES" 和 a, b, c。否则，就说明用这种方法找不到，那很可能就是真的找不到了，就输出 "NO" 吧，呜...

题解

光说不练可不行喵~ 下面是具体的 C++ 代码实现，我已经加上了详细的注释，就像给鱼干撒上木鱼花一样美味~

cpp

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

void solve() {
    long long n;
    std::cin >> n;

    // 用一个 vector 来存放我们找到的因数 a 和 b
    std::vector<long long> factors;
    long long temp_n = n;

    // 步骤 1: 寻找最小的因数 'a'
    // 我们从 2 开始循环，直到 i*i > temp_n。这是一个找最小因数的标准优化方法！
    for (long long i = 2; i * i <= temp_n; ++i) {
        if (temp_n % i == 0) {
            factors.push_back(i); // 找到了！它就是 a
            temp_n /= i;          // 更新 n，为寻找下一个因数做准备
            break;                // 找到最小的就跑，不能再贪心了喵
        }
    }

    // 如果连一个因数 a 都没找到，说明 n 是个质数，不可能啦
    if (factors.empty()) {
        std::cout << "NO\n";
        return;
    }

    // 步骤 2: 寻找第二个因数 'b'
    // 为了保证 b 和 a 不一样，我们从 a+1 开始搜索
    for (long long i = factors[0] + 1; i * i <= temp_n; ++i) {
        if (temp_n % i == 0) {
            factors.push_back(i); // 找到了！它就是 b
            temp_n /= i;          // 再次更新 n
            break;                // 同样，找到一个就够了
        }
    }

    // 如果只找到了 a，没找到 b，那也不行
    if (factors.size() < 2) {
        std::cout << "NO\n";
        return;
    }

    // 步骤 3 & 4: 确定 c 并进行最终检查
    long long c = temp_n; // 剩下的部分就是 c

    // c 必须大于 1，并且不能和 a、b 重复
    if (c > 1 && c != factors[0] && c != factors[1]) {
        // 完美！找到了三个不同的小伙伴！
        std::cout << "YES\n";
        std::cout << factors[0] << " " << factors[1] << " " << c << "\n";
    } else {
        // 呜... c 不合格，宣告失败
        std::cout << "NO\n";
    }
}

int main() {
    // 这两行是为了让输入输出快一点，是竞赛中的常用小技巧哦~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

做完题当然要总结一下知识点，这样才能不断进步，成为更厉害的程序员主人喵！

整数的因数分解 (Integer Factorization) 这道题的核心就是整数分解。简单来说，就是把一个合数（非质数）写成几个数的乘积。比如 12 = 2 * 2 * 3。这是数论中的一个基础又非常重要的话题。
试除法 (Trial Division) 我们在代码中找因数的方法，就是最经典、最简单的“试除法”。我们想找 n 的一个因数，就从最小的质数 2 开始，挨个尝试 2, 3, 4, 5, ... 看谁能整除 n。优化：为什么只到 sqrt(n) 就够了呢？因为如果一个数 n 有一个大于 sqrt(n) 的因数 d，那么 n/d 必然是一个小于 sqrt(n) 的因数。所以，如果我们检查到 sqrt(n) 都没找到因数，那这个数就只能是质数啦（或者 1）。这是一个非常重要的优化技巧哦！不然当 n 很大的时候，程序会跑得像乌龟一样慢。
贪心算法 (Greedy Algorithm) 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。在这道题里，我们贪心地选择最小的因数，为后续的选择留出最大的可能性，最终成功地解决了问题。是不是很聪明呢？喵~

好啦，今天的解题就到这里啦！希望我的讲解能帮到主人哦~ 如果还有什么问题，随时可以再来找我玩！喵~

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍