手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

[算法总结] 约数 !

时间:2021/5/27 10:47:59|来源:|点击: 次

约数

  • 871. 约数之和(O√n +M log M)
    • 细节:
    • Code:

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;
}

Copyright © 2002-2019 某某自媒体运营 版权所有