[AcWing]869. 试除法求约数（C++实现）试除法求约数模板题

[AcWing]869. 试除法求约数（C++实现）试除法求约数模板题

[AcWing]869. 试除法求约数（C++实现）试除法求约数模板题

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

1. 题目

2. 读题（需要重点注意的东西）

思路：

什么是约数？
约数，又称因数。整数a除以整数b(b≠0)，除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。

3. 解法

---------------------------------------------------解法---------------------------------------------------

#include 
#include 
#include 

using namespace std;

vector get_divisors(int x)
{
    vector res;
    for (int i = 1; i <= x / i; i ++ ) // 为什么是X/i见下方可能有帮助的前置习题
        if (x % i == 0)
        {
            res.push_back(i);
            // 如果i是x的约数，那么x/i也是x的约数，但是要判断一下，当i != x/i时，再加入，避免重复
            if (i != x / i) res.push_back(x / i); 
        }
    sort(res.begin(), res.end());
    return res;
}

int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        int x;
        cin >> x;
        auto res = get_divisors(x);

        for (auto x : res) cout << x << ' ';
        cout << endl;
    }

    return 0;
}

4. 可能有帮助的前置习题

• [AcWing]866. 试除法判定质数（C++实现）试除法判定质数模板题

5. 所用到的数据结构与算法思想

• 试除法

6. 总结

试除法求约数的模板题，熟记并背下来。