【C++】合計がNに等しく積が最大となるNの4つの約数の求め方（Set-2）

概要

ある整数Nが与えられたとき、Nのすべての約数を調査し、以下の2つの条件を同時に満たす「4つの約数の組み合わせ」を見つけて、その積を出力するのが本記事の目的です。

• 4つの約数の合計がNと等しいこと
• 4つの約数の積が最大であること

条件を満たす4つの約数が存在しない場合は「Not possible（不可能）」と出力します。なお、積を最大化するという観点から、4つの約数がすべて同じ値であっても問題ありません。

入力例

N = 60

出力例

All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60
Product is -> 50625

この例では、約数「15」を4つ選択しています。

15 + 15 + 15 + 15 = 60 となり、このとき積（15 × 15 × 15 × 15 = 50625）が最大になります。

解法のアプローチ

まず基本となるのは、計算量 O(P³)（PはNの約数の個数）のシンプルな全探索手法です。さらに、以下の手順に従うことで、時間計算量 O(N²) のより効率的な方法を実現できます。

• 与えられた数のすべての約数をコンテナに格納します。
• すべてのペアに対して反復処理を行い、その和を別のコンテナに保存します。
• どの要素からその和が作られたかを復元できるよう、インデックス（要素1＋要素2）に対してペア（要素1, 要素2）を記録します。
• 再びすべてのペアの和に対して反復処理を行い、「n − ペアの和」が同じコンテナ内に存在するかどうかを確認します。存在すれば、2組のペアによって目的の4つ組が構成できます。
• ペア用のハッシュ配列を実装し、各和を構成していた元の要素を取得できるようにします。
• 最後に、条件を満たすすべての4つ組の中で最大の積を保持し、結果として出力します。

C++による実装例

// C++プログラム：合計がNに等しく、積が最大となる
// Nの4つの約数を求める
#include <bits/stdc++.h>
using namespace std;

// 約数を求め、4つの約数の積を出力する関数
void findfactors1(int q){
    vector<int> vec1;
    // すべての約数をベクターに挿入する
    for (int i = 1; i * i <= q; i++) {
        if (q % i == 0) {
            vec1.push_back(i);
            vec1.push_back(q / i);
        }
    }
    // ベクターをソートする
    sort(vec1.begin(), vec1.end());
    // すべての約数を出力する
    cout << "All the factors are -> ";
    for (int i = 0; i < vec1.size(); i++)
        cout << vec1[i] << " ";
    cout << endl;
    // あらゆる整数は1で割り切れるため初期値を設定
    int maxProduct1 = 1;
    bool flag1 = 1;
    // 3重ループで最初の3つの約数を決定する
    for (int i = 0; i < vec1.size(); i++) {
        for (int j = i; j < vec1.size(); j++) {
            for (int k = j; k < vec1.size(); k++) {
                // 4つ目の約数を y として求める
                int y = q - vec1[i] - vec1[j] - vec1[k];
                // 4つ目の約数が負になったらループを抜ける
                if (y <= 0)
                    break;
                // より良い積が見つかった場合は更新する
                if (q % y == 0) {
                    flag1 = 0;
                    maxProduct1 = max(vec1[i] * vec1[j] * vec1[k] * y, maxProduct1);
                }
            }
        }
    }
    // 条件を満たす組み合わせが存在すれば積を出力する
    if (flag1 == 0)
        cout << "Product is -> " << maxProduct1 << endl;
    else
        cout << "Not possible" << endl;
}

// ドライバーコード
int main(){
    int q;
    q = 60;
    findfactors1(q);
    return 0;
}

実行結果

All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60
Product is -> 50625

コードのポイント

この実装では、約数の列挙を √N までのループで行い、i と q/i を同時にベクターへ追加することで効率化しています。その後、3重ループで最初の3つの約数を固定すれば、4つ目の約数は「y = q − 3つの約数の合計」として一意に決まります。y が正の整数であり、かつ q の約数である（q % y == 0）場合にのみ、積の最大値を更新していく仕組みです。

また、「合計が固定された4数の積は、各数ができるだけ等しいときに最大化される」という性質（相加平均と相乗平均の関係）があります。そのため、Nが4で割り切れる場合は N/4 を4つ選ぶ組み合わせが最適解となることが多く、上記の例でも 60 ÷ 4 = 15 が選ばれています。