Board logo

標題: 202412潛力1-因數分解 (Factors) [打印本頁]
作者: may    時間: 2025-1-29 17:45     標題: 202412潛力1-因數分解 (Factors)

問題敘述
給定一正整數P，進行因數分解後得到n個正整數a1, a2, …, an，即a1 × a2 × … × an = P，且已知2 ≤ a1 ≤ a2 ≤ … ≤ an ≤ 9。
請寫一個程式，給定P找出a1, a2, …, an。 如果找不到滿足以上條件的因數分解，則視為無解。
如果存在多組解，請輸出長度最短的那組解，也就是n最小的。如果仍然有多組解長度一樣，請輸出字典序最小的，也就是先找出a1最小的那組解，如果仍有多組解a1同樣最小，則找出a2最小的那組解，……，以此類推，到最後找出an最小的那組解。
例如：給定P = 24，其中有兩組解的長度最短: a1 = 3、a2 = 8；a1 = 4、a2 = 6。由於「a1 = 3、a2 = 8」這一組解的字典序小於另外一組解「a1 = 4、a2 = 6」，因此它就是答案。
輸入格式:第一列有一個正整數P ( 2 ≤ P ≤ 1018 )，表示要進行因數分解的P。
輸出格式:請輸出一列正整數，相鄰兩數以一個空白隔開，分別表示a1, a2, …, an。如果無解，請以-1表示。
輸入範例1: 24        輸出範例1:  3 8
輸入範例2: 22        輸出範例2:  -1
輸入範例3:  8         輸出範例3:   8
輸入範例4:   6561   輸出範例4:   9 9 9 9
評分說明:   此題目測資分成三組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。 第一組 (25 分)：P ≤ 103 第二組 (25 分)：P為2的冪次方 第三組 (50 分)：無特別限制。
作者: may    時間: 2025-1-29 18:33

  1. #include<bits/stdc++.h>
  2. //#include <iostream>
  3. //#include <vector>
  4. //#include <algorithm>

  6. using namespace std;

  8. // 將 P 分解為 2~9 之間的因數，確保是「最短長度」且「字典序最小」
  9. vector<int> factorize(long long P) {
  10.     if (P < 2) return {-1}; // P 必須 ≥ 2

  12.     vector<int> factors;

  14.     // 嘗試從 9 到 2 進行分解
  15.     for (int d = 9; d >= 2; --d) {
  16.         while (P % d == 0) {
  17.             factors.push_back(d);
  18.             P /= d;
  19.         }
  20.     }

  22.     // 如果 P 無法完全分解為 2~9 的數字，則回傳 -1
  23.     if (P != 1) return {-1};

  25.     // **確保字典序最小（數字越小越排前）**
  26.     sort(factors.begin(), factors.end());

  28.     return factors;
  29. }

  31. int main() {
  32.     long long P;
  33.     cin >> P;

  35.     vector<int> result = factorize(P);

  37.     // 輸出結果
  38.     if (result.size() == 1 && result[0] == -1) {
  39.         cout << -1 << endl;
  40.     } else {
  41.         for (size_t i = 0; i < result.size(); ++i) {
  42.             if (i > 0) cout << " ";
  43.             cout << result[i];
  44.         }
  45.         cout << endl;
  46.     }

  48.     return 0;
  49. }
  50. /*
  51. 輸入範例1: 24        輸出範例1:  3 8
  52. 輸入範例2: 22        輸出範例2:  -1
  53. 輸入範例3:  8        輸出範例3:  8
  54. 輸入範例4: 6561      輸出範例4:  9 9 9 9
  55. */
複製代碼
作者: may    時間: 2025-1-29 18:41

解題思路
質因數分解：

由於可用的數字範圍是 2 到 9，我們需要將
P 盡量拆解成這些數字的乘積。
先從 9 開始，嘗試將
P 除盡，再來是 8，依序到 2。
組合與排序：

我們希望找出最短的分解組合，因此我們從大數字開始分解，能用大的就用大的，確保乘數數量最少。
如果有多種相同長度的解，我們需要選擇字典序最小的（較小的數要放前面）。
邊界條件：

若 P 已經是 2 到 9 之間的數字，則直接輸出它本身。
若無法完全拆解（例如 22，其質因數為 2 和 11，而 11 不在 2 到 9 的範圍內），則輸出 -1。
-------------
總結
這個演算法使用 貪婪法 來確保因數數量最少，然後 排序 來確保字典序最小。
這樣的設計確保了 時間複雜度低，結果符合題目要求，並且 容易理解與實作。
這樣的解法應該能夠通過所有測試資料，包括大數據範圍的測試！
--------------------------------------
-[attach]20608[/attach]
-------------------------------------
總結
這個演算法使用 貪婪法 來確保因數數量最少，然後 排序 來確保字典序最小。
這樣的設計確保了 時間複雜度低，結果符合題目要求，並且 容易理解與實作。
這樣的解法應該能夠通過所有測試資料，包括大數據範圍的測試！
----------------------------------------------------------------------
✅ 不強制拆解 8、6、4，而是保留它們，讓長度最短！
✅ 確保字典序最小，正確輸出最小 lexicographical order！
✅ 能夠正確處理所有測試案例，包括 2 的冪次方、大數字等！



歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/) Powered by Discuz! 7.2