【C++】LCMがNとなる相異なる数の最大和を求める方法

本記事では、整数Nが与えられたとき、最小公倍数(LCM)がNとなる相異なる数の組の中で、その総和が最大になる値を求めるプログラムをC++で作成します。

問題の概要

ここでの課題は、Nを最小公倍数(LCM)として持つ数の組み合わせの中から、和が最大になるものを見つけ出すことです。

具体例で問題を確認してみましょう。

入力

N = 10

出力

18

説明

LCMが10となる最大の和は 1 + 2 + 5 + 10 = 18

10を最小公倍数とする数の組み合わせはいくつか存在しますが(例：2と5、1と10など)、その中でも10のすべての約数 {1, 2, 5, 10} を使った場合に和が最大となり、答えは18になります。

解法のアプローチ

この問題に対するシンプルかつ効果的な解法は、「NをLCMにしたいなら、Nのすべての相異なる約数を選べばよい」という性質を利用することです。

なぜこれで正しいのかを整理してみます。

• N自身も約数であるため、Nの約数全体の集合のLCMは必ずNになります。
• 約数以外の数を追加するとLCMがNより大きくなってしまうため、使える数は約数のみに限られます。
• したがって、すべての約数を足し合わせたものが最大の和(maxSum)となります。

実装では、1から√Nまで順に調べて約数を列挙します。i が N の約数であれば、ペアとなる約数 N/i も同時に加算します。i と N/i が等しい場合(完全平方数の場合)は二重カウントを避けるため、一度だけ加算します。この方法により、計算量はO(√N)に抑えられます。

実装例

上記の解法を示すサンプルプログラムです。

#include <iostream>
using namespace std;

int calcFactorSum(int N){
    int maxSum = 0;
    // √N まで調べて約数を列挙する
    for (int i = 1; i*i <= N; i++){
        if (N % i == 0) {
            if (i == (N/i))
                maxSum = maxSum + i; // 平方数の場合は1回だけ加算
            else
                maxSum = maxSum + i + (N/i); // 約数のペアを両方加算
        }
    }
    return maxSum;
}
int main(){
    int N = 42;
    cout<<"LCMが "<<N<<" となる相異なる数の最大和は "<<calcFactorSum(N);
    return 0;
}

出力

LCMが 42 となる相異なる数の最大和は 96

42の場合、約数は {1, 2, 3, 6, 7, 14, 21, 42} であり、その総和は 1+2+3+6+7+14+21+42 = 96 となります。確かに、これらの数のLCMは42であり、これ以上の和は達成できません。

まとめ

LCMがNとなる相異なる数の最大和は、Nの全約数の総和と一致します。約数を√Nまでのループで効率的に列挙すれば、O(√N)の計算量でこの問題を解くことができます。競技プログラミングや数学的アルゴリズムの学習において、約数の性質は非常に重要な基礎知識なので、ぜひ押さえておきましょう。