Divisor
(math/number-theory/divisor.hpp)

• View this file on GitHub
• Last update: 2024-01-08 17:31:43+09:00
• Include: #include "math/number-theory/divisor.hpp"

Description

$n$ の約数を試し割り法で全て求める．

Operations

• vector<long long> divisor(long long n)
  • $n$ の約数を昇順で返す
  • 時間計算量: $O(\sqrt{n})$

Code

#pragma once
#include <vector>

std::vector<long long> divisor(long long n) {
    std::vector<long long> ret1, ret2;
    for (long long i = 1; i * i <= n; ++i) {
        if (i * i == n) {
            ret1.push_back(i);
        } else if (n % i == 0) {
            ret1.push_back(i);
            ret2.push_back(n / i);
        }
    }
    ret1.insert(ret1.end(), ret2.rbegin(), ret2.rend());
    return ret1;
}

#line 2 "math/number-theory/divisor.hpp"
#include <vector>

std::vector<long long> divisor(long long n) {
    std::vector<long long> ret1, ret2;
    for (long long i = 1; i * i <= n; ++i) {
        if (i * i == n) {
            ret1.push_back(i);
        } else if (n % i == 0) {
            ret1.push_back(i);
            ret2.push_back(n / i);
        }
    }
    ret1.insert(ret1.end(), ret2.rbegin(), ret2.rend());
    return ret1;
}

Back to top page