題解：試除法求約數
題目傳送門
869. 試除法求約數
一、題目描述
給定 n 個正整數 a?，對于每個整數 a?，按照從小到大的順序輸出它的所有約數。
輸入格式：
- 第一行包含整數 n
- 接下來 n 行，每行包含一個整數 a?
輸出格式：
- 共 n 行，其中第 i 行輸出第 i 個整數 a? 的所有約數
數據范圍：
- 1 ≤ n ≤ 100
- 1 ≤ a? ≤ 2×10?
二、題目分析
我們需要為每個給定的數 a? 找出它的所有約數，并按升序排列輸出。約數是指能整除該數的整數。
三、解題思路
使用試除法來高效地找出所有約數：
- 遍歷從1到√a?的所有整數
- 如果當前整數 i 能整除 a?，則 i 和 a?/i 都是約數
- 將找到的約數存入數組并排序后輸出
四、算法講解
試除法是求約數的經典方法：
- 對于數 a，我們只需要檢查1到√a的范圍
- 當發現 i 是約數時，同時記錄 i 和 a/i（除非兩者相同）
- 最后將所有約數排序輸出
例子：
對于 a = 6：
- 檢查1：6%1=0 → 記錄1和6
- 檢查2：6%2=0 → 記錄2和3
- 不需要檢查>√6≈2.45的數
- 得到約數1,2,3,6 → 排序后輸出
五、代碼實現
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 110;
int n;
int a[N];void solve()
{cin >> n;while(n -- ){int a;cin >> a;vector<int> s; // 存儲約數的動態數組// 試除法求約數for (int i = 1; i <= a / i; i ++) // 只需遍歷到sqrt(a){if (a % i == 0) // 如果i是約數{s.push_back(i); // 加入iif (i != a / i) // 避免重復加入平方數的情況s.push_back(a / i); // 加入對應的另一個約數}}sort(s.begin(), s.end()); // 將約數排序// 輸出結果for (int c : s)cout << c << " ";cout << "\n";}
}signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}
六、重點細節
- 遍歷范圍：只需遍歷到√a（即i ≤ a/i），可以大幅減少計算量
- 避免重復：當i = a/i時（即a是完全平方數），只需加入一次
- 排序輸出：找到的約數是無序的，需要排序后輸出
七、復雜度分析
- 時間復雜度：O(n × (√a? + k log k))，其中k是約數個數
- 對于每個數a?，試除法需要O(√a?)時間
- 排序約數需要O(k log k)時間，k通常很小
- 空間復雜度：O(k)，存儲約數需要的空間
八、總結
試除法是求解約數問題的高效方法，通過只遍歷到平方根來優化性能。本題的關鍵在于正確實現試除法，并注意處理完全平方數的情況。代碼簡潔高效，適合處理給定范圍內的輸入數據。
)
