旅游网站哪个做的好,女与男爱做电影网站免费,网页设计尺寸1080,网站flash题解#xff1a;试除法求约数
题目传送门
869. 试除法求约数
一、题目描述
给定 n 个正整数 aᵢ#xff0c;对于每个整数 aᵢ#xff0c;按照从小到大的顺序输出它的所有约数。
输入格式#xff1a;
第一行包含整数 n接下来 n 行#xff0c;每行包含一个整数 aᵢ
输…题解试除法求约数
题目传送门
869. 试除法求约数
一、题目描述
给定 n 个正整数 aᵢ对于每个整数 aᵢ按照从小到大的顺序输出它的所有约数。
输入格式
第一行包含整数 n接下来 n 行每行包含一个整数 aᵢ
输出格式
共 n 行其中第 i 行输出第 i 个整数 aᵢ 的所有约数
数据范围
1 ≤ n ≤ 1001 ≤ aᵢ ≤ 2×10⁹
二、题目分析
我们需要为每个给定的数 aᵢ 找出它的所有约数并按升序排列输出。约数是指能整除该数的整数。
三、解题思路
使用试除法来高效地找出所有约数
遍历从1到√aᵢ的所有整数如果当前整数 i 能整除 aᵢ则 i 和 aᵢ/i 都是约数将找到的约数存入数组并排序后输出
四、算法讲解
试除法是求约数的经典方法
对于数 a我们只需要检查1到√a的范围当发现 i 是约数时同时记录 i 和 a/i除非两者相同最后将所有约数排序输出
例子 对于 a 6
检查16%10 → 记录1和6检查26%20 → 记录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;vectorint 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)存储约数需要的空间
八、总结
试除法是求解约数问题的高效方法通过只遍历到平方根来优化性能。本题的关键在于正确实现试除法并注意处理完全平方数的情况。代码简洁高效适合处理给定范围内的输入数据。
