871. 约数之和(O√n +M log M)

细节:

因为ai的范围是 2e9+10

所以 如果使用 On的暴力枚举是必然超过的

借用@Bug-Free一张图

///若d > √n 是 N的约数
///则 N/d <= √n 也是N 的约数
///换言之 约数总是成对出现的(除了完全平方数)

因此因为这个关系

所以y总的代码就把时间复杂度改成O√n +M log M
(M表示的是 约数的个数)

Code:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(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;
}