競プロノート

Appearance

約数列挙（Divisor Enumeration） ​

整数Nの正の約数をすべて列挙する。

約数はペアで現れる性質を利用して、O(√N)で求められる。

特徴 ​

項目内容
用途正の約数の列挙
計算量O(√N)
空間計算量O(d(N))
前処理不要

d(N)はNの正の約数の個数。

考え方 ​

Nの約数dが存在するとき、N/dも約数となる。

例えばN=36なら、

text
1 × 36
2 × 18
3 × 12
4 × 9
6 × 6

したがって、√N以下を調べるだけで、すべての約数を取得できる。

  • 小さい約数は昇順に格納する。
  • 対応する大きい約数は降順に格納する。
  • 大きい約数の配列を反転して結合すれば昇順になる。

実装 ​

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> divisors(ll n) {
    assert(n >= 1);
    vector<ll> small, large;
    for (ll d = 1; d <= n / d; d++) {
        if (n % d != 0) continue;
        small.push_back(d);
        if (d != n / d) large.push_back(n / d);
    }
    reverse(large.begin(), large.end());
    small.insert(small.end(), large.begin(), large.end());
    return small;
}

int main() {
    ll n;
    cin >> n;
    for (ll d : divisors(n)) cout << d << ' ';
    cout << '\n';
}

使用例 ​

入力

text
36

出力

text
1 2 3 4 6 9 12 18 36

返り値は vector<ll> で昇順に格納される。

cpp
auto ds = divisors(36);
// {1, 2, 3, 4, 6, 9, 12, 18, 36}

典型的な応用 ​

約数の個数 ​

cpp
int cnt = divisors(n).size();

約数の総和 ​

cpp
ll sum = 0;
for (ll d : divisors(n)) sum += d;

約数を利用した全探索 ​

約数となり得る値だけを列挙することで、探索候補を減らせる。

cpp
for (ll d : divisors(n)) {
    // dを候補として処理
}

注意点 ​

  • Nは1以上とする。
  • N=1の場合、約数は {1}。
  • 完全平方数の場合、√Nを重複して追加しない。
  • d*d <= n はオーバーフローする可能性があるため、d <= n/d が安全。
  • 約数の列挙と素因数分解は異なる。
  • 非常に大きなNでは、O(√N)でも時間がかかる場合がある。

関連 ​