C++で自然数のすべての約数の約数の総和を求める方法

この問題では、自然数 N が与えられ、N のすべての約数について、それぞれが持つ約数の総和を求め、それらをすべて合計するという課題に取り組みます。

問題の例

入力：N = 12
出力：55

説明：

12 の約数は「1, 2, 3, 4, 6, 12」の 6 個です。各約数の約数の総和は以下のようになります。

1  → (1) = 1
2  → (1 + 2) = 3
3  → (1 + 3) = 4
4  → (1 + 2 + 4) = 7
6  → (1 + 2 + 3 + 6) = 12
12 → (1 + 2 + 3 + 4 + 6 + 12) = 28

合計 = 1 + 3 + 4 + 7 + 12 + 28 = 55

解法アプローチ：素因数分解を活用

この問題は、N を素因数分解することで効率的に解くことができます。N を次のように素因数分解したとき、

N = p1c1 × p2c2 × … × pkck

答えは各素因子に対応する項の積として表せます。素因子 p の指数が c である場合、対応する項は次の式になります。

(c+1)·p0 + c·p1 + (c−1)·p2 + … + 1·pc

この性質を利用すれば、すべての約数を実際に列挙しなくても、素因数分解の結果だけから答えを高速に計算できます。

N = 12 の場合の計算例

12 = 2² × 3¹ なので、

• p = 2、c = 2 のとき：3×1 + 2×2 + 1×4 = 11
• p = 3、c = 1 のとき：2×1 + 1×3 = 5

よって答えは 11 × 5 = 55 となります。

C++ 実装例

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

int findSumOfDivisorsOfDivisors(int n) {
    map<int, int> factorCount;
    for (int j = 2; j <= sqrt(n); j++) {
        int count = 0;
        while (n % j == 0) {
            n /= j;
            count++;
        }
        if (count)
            factorCount[j] = count;
    }
    if (n != 1)
        factorCount[n] = 1;

    int sumOfDiv = 1;
    for (auto it : factorCount) {
        int power = 1;
        int sum = 0;
        for (int i = it.second + 1; i >= 1; i--) {
            sum += (i * power);
            power *= it.first;
        }
        sumOfDiv *= sum;
    }
    return sumOfDiv;
}

int main() {
    int n = 12;
    cout << "すべての約数の約数の総和: " << findSumOfDivisorsOfDivisors(n);
    return 0;
}

実行結果

すべての約数の約数の総和: 55

計算量

このアルゴリズムは √N までの試し割りで素因数分解を行うため、時間計算量は O(√N) です。約数をすべて列挙し、それぞれの約数の和を個別に計算する素朴な手法と比べて、はるかに効率的です。

まとめ

自然数 N のすべての約数の約数の総和は、素因数分解の結果をもとに、各素因子ごとに「(c+1)p⁰ + cp¹ + … + 1·p^c」という項を計算して掛け合わせることで、O(√N) で効率よく求められます。