题解：AcWing 869 试除法求约数

【题目来源】

AcWing：869. 试除法求约数 - AcWing题库

【题目描述】

给定 \(n\) 个正整数 \(a_i\)，对于每个整数 \(a_i\)，请你按照从小到大的顺序输出它的所有约数。

【输入】

第一行包含整数 \(n\)。

接下来 \(n\) 行，每行包含一个整数 \(a_i\)。

【输出】

输出共 \(n\) 行，其中第 \(i\) 行输出第 \(i\) 个整数 \(a_i\) 的所有约数。

【输入样例】

2
6
8

【输出样例】

1 2 3 6 
1 2 4 8 

【算法标签】

《AcWing 869 试除法求约数》 #数学知识# #约数# #试除法#

【代码详解】

#include <bits/stdc++.h>
using namespace std;int n; // 定义整数 n，表示输入的数的个数
vector<int> res; // res 用于存储一个数的所有约数// 获取一个数的所有约数
void get_divisors(int n)
{for (int i = 1; i <= n / i; i++) { // 遍历 1 到 sqrt(n) 的所有整数if (n % i == 0) { // 如果 i 是 n 的约数res.push_back(i); // 将 i 加入 resif (i != n / i) res.push_back(n / i); // 如果 i 和 n/i 不相等，将 n/i 加入 res}}sort(res.begin(), res.end()); // 对 res 进行排序
}int main()
{cin >> n; // 输入数的个数 nwhile (n--) { // 遍历每个数int x; // 定义整数 xcin >> x; // 输入 xres.clear(); // 清空 resget_divisors(x); // 获取 x 的所有约数for (auto t : res) cout << t << " "; // 输出 x 的所有约数cout << endl; // 换行}return 0; // 程序结束
}

【运行结果】

2
6
1 2 3 6
8
1 2 4 8