Divisor(約数列挙)
(src/math/Divisor.hpp)

• View this file on GitHub
• Last update: 2022-08-15 18:33:06+09:00
• Include: #include "src/math/Divisor.hpp"

概要

std::vector<long long> divisor(long long x)

試し割りを用いた素朴な約数列挙

機能

• divisor(long long x): xを約数列挙します。xは64ビットに収まる0以上の整数である必要があります。

計算量

• $O(\sqrt(x))$

Verified with

• test/aoj_itp1_3_d.test.cpp

Code

#pragma once

#include <vector>
#include <algorithm>

namespace zawa {

    std::vector<long long> divisor(long long x) {
        std::vector<long long> res;

        for (long long i = 1 ; i * i <= x ; i++) {
            if (x % i) continue;
            res.emplace_back(i);
            if (i * i != x) res.emplace_back(x / i);
        }
        std::sort(res.begin(), res.end());

        return res;
    }

}// namespace zawa

#line 2 "src/math/Divisor.hpp"

#include <vector>
#include <algorithm>

namespace zawa {

    std::vector<long long> divisor(long long x) {
        std::vector<long long> res;

        for (long long i = 1 ; i * i <= x ; i++) {
            if (x % i) continue;
            res.emplace_back(i);
            if (i * i != x) res.emplace_back(x / i);
        }
        std::sort(res.begin(), res.end());

        return res;
    }

}// namespace zawa

Back to top page