ACM 題 HDU 5428 The Factor：最小合格因子求解與 AC 代碼詳解

題目重述

給定 n 個正整數，求它們乘積的**最小因子**，該因子擁有**超過 2 個因子**（含 1 和自身）。即：找最小的**非質數且非質數平方**的因子。若不存在輸出 -1。

關鍵觀察

• 乘積極大（≤ 2e9^100），**不可直接計算乘積**，必須在質因子分解層面處理。
• 合格因子 = 至少有 3 個因數的數 = **合數且非質數平方**（質數平方如 4=2² 有 3 個因子 1,2,4 **符合**；質數只有 2 個因子 **不符合**）。
• 最小合格因子必為：**最小質因子的平方**（如 2²=4），或 **兩個最小質因子的乘積**（如 2×3=6），取較小者。

算法流程

1. 對每個 a[i] 質因子分解，**只保留最小的兩個質因子**（含重複，如 8=2×2×2 保留 2,2）。
2. 將所有保留的質因子收集到數組 b[]，排序。
3. 若 b.size < 2 輸出 -1；否則輸出 b[0] * b[1]（已保證為最小合格因子）。

AC 代碼

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
LL a[111], b[111111];
int main() {
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            LL x = a[i];
            int got = 0;
            for (LL p = 2; p * p <= x && got < 2; p++) {
                while (x % p == 0 && got < 2) {
                    b[++cnt] = p;
                    x /= p;
                    got++;
                }
            }
            if (x > 1 && got < 2) { // 剩下一個大質因子
                b[++cnt] = x;
                got++;
            }
        }
        if (cnt < 2) cout << -1 << '\n';
        else {
            sort(b + 1, b + cnt + 1);
            cout << b[1] * b[2] << '\n';
        }
    }
    return 0;
}

易錯點總結

• 質因子分解循環條件 p * p <= x 動態縮小上界，避免 TLE。
• 同一質因子可重複計入（如 8 產生兩個 2），got < 2 控制每個數最多貢獻兩個因子。
• 大質因子殘留（如 26=2×13）需補入，否則漏掉 13 導致錯誤。
• 輸出類型用 long long，乘積可能超 32 位。

本題核心在於**「因子個數 > 2」等價於「非質數」**，並利用「最小質因子組合」構造答案，避開大數乘積陷阱。