C++で合計がNに等しく、積が最大となる4つの約数を見つける方法

整数 N が与えられたとき、N の約数の中から4つを選び、次の2つの条件を同時に満たす組み合わせの積を求めることを考えます。

• 選んだ4つの約数の合計が N に等しいこと
• 4つの約数の積が最大になること

例として N = 24 の場合を考えてみましょう。24 の約数は 1, 2, 3, 4, 6, 8, 12, 24 です。この中から「6」を4回選ぶと、6 + 6 + 6 + 6 = 24 という合計になり、このときの積は 6 × 6 × 6 × 6 = 1296 となり、これが最大値になります。

解法のアプローチ

この問題を解くには、まず 1 から N までの各整数について約数をすべて求め、その上で以下の条件を順に確認します。

• N が素数の場合： 条件を満たす4つの約数の組み合わせが存在しないため、答えは false（-1）となります。
• N が 4 で割り切れる場合： 答えは x⁴ となります。ここで x は N ÷ 4 の商です。N/4 を4回足せば N になり、同じ値の積が最大になるためです。
• その他の場合： 答えには、約数リストの後ろから3番目の約数が2回含まれる必要があります。残りの2つの約数については、ネストしたループで全組み合わせを探索します。

C++での実装例

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool isPrime(int n) {
   if (n <= 1)
      return false;
   if (n <= 3)
      return true;
   if (n % 2 == 0 || n % 3 == 0)
      return false;
   for (int i = 5; i * i <= n; i = i + 6)
      if (n % i == 0 || n % (i + 2) == 0)
   return false;
   return true;
}
void get_factors(int N, vector<int> fact_vectors[]) {
   for (int i = 2; i < N; i++) {
      for (int j = 1; j * j <= i; j++) {
         if (i % j == 0) {
            if (i / j == j)
            fact_vectors[i].push_back(j);
            else {
               fact_vectors[i].push_back(j);
               fact_vectors[i].push_back(i / j);
            }
         }
      }
      sort(fact_vectors[i].begin(), fact_vectors[i].end());
   }
}
int getProduct(int n) {
   vector<int> v[n + 100];
   get_factors(n + 100, v);
   if (n % 4 == 0) {
      int x = n / 4;
      x *= x;
      return x * x;
   } else {
      if (isPrime(n))
      return -1;
      else {
         int ans = -1;
            if (v[n].size() > 2) {
               int fac = v[n][v[n].size() - 3];
               for (int i = v[n].size() - 1; i >= 0; i--) {
                  for (int j = v[n].size() - 1; j >= 0; j--) {
                     if ((fac * 2) + (v[n][j] + v[n][i]) == n)
                     ans = max(ans, fac * fac * v[n][j] * v[n][i]);
                  }
               }
            return ans;
         }
      }
   }
}
int main() {
   int n = 24;
   cout << "The product is: " << getProduct(n);
}

出力結果

The product is: 1296

コードの解説

このプログラムは、大きく分けて3つの部分で構成されています。

• isPrime 関数： 6k ± 1 の最適化を使った素数判定を行います。試し割り法を √n まで確認することで効率的に判定できます。
• get_factors 関数： 各整数について、√i までループして約数をペアで求め、昇順にソートして格納します。
• getProduct 関数： メインのロジックです。N が 4 の倍数なら (N/4)⁴ を即座に返し、素数なら -1 を返します。それ以外の場合は、後ろから3番目の約数を2回使用する前提で、残りの2つの約数を二重ループで探索し、条件を満たす最大の積を求めます。

なお、N が 4 の倍数の場合に (N/4)⁴ が最適解となるのは、算術平均・幾何平均の不等式（相加平均 ≥ 相乗平均）により、合計が固定されたとき積は各要素が等しいときに最大化されるためです。