C++でN未満の2つの数の倍数の合計を求める方法

問題概要

この問題では、3つの整数 M1、M2、N が与えられます。求めるのは、N 未満に存在する M1 と M2 の倍数をすべて足し合わせた合計値です。

つまり、N 未満の数のうち、M1 または M2 の倍数に該当するものをすべて加算します。

問題を理解するための例

入力：

N = 13, M1 = 4, M2 = 6

出力：

30

解説： 13 未満で 4 または 6 の倍数となる数は「4, 6, 8, 12」です。したがって合計は 4 + 6 + 8 + 12 = 30 となります。

解法1：シンプルな全探索アプローチ

最も基本的な解決策は、1 から N 未満まで順にループ処理を行い、M1 または M2 で割り切れる値をすべて加算していく方法です。

アルゴリズム

ステップ1： sum = 0、i = 1 として初期化し、i が N 未満である間ループを回します。

ステップ1.1： i % M1 == 0 または i % M2 == 0 が成立する場合、sum += i を実行します。

ステップ2： ループ終了後、sum を返します。

サンプルコード

#include <iostream>
using namespace std;

int calcMulSum(int N, int M1, int M2){
    int sum = 0;
    for (int i = 0; i < N; i++)
        if (i % M1 == 0 || i % M2 == 0)
            sum += i;
    return sum;
}

int main(){
    int N = 24, M1 = 4, M2 = 7;
    cout << "The sum of multiples of " << M1 << " and " << M2 << " below " << N << " is " << calcMulSum(N, M1, M2);
    return 0;
}

実行結果

The sum of multiples of 4 and 7 below 24 is 102

この方法でも正しい結果が得られますが、1 から N までのすべての数を順に確認する必要があるため、時間計算量は O(n) となります。N が大きくなると処理が遅くなるため、必ずしも最適な解法とは言えません。

解法2：数学的公式を使った効率的なアプローチ

より優れた解法が、等差数列の和の公式を活用する方法です。

ここでのポイントは包除原理です。M1 の倍数の和と M2 の倍数の和を単純に足し合わせると、両者に共通する倍数（ここでは簡単のため M1×M2 の倍数とします）が二重にカウントされてしまいます。そこで、最終的な合計は次のように表せます。

合計 ＝ M1の倍数の和 ＋ M2の倍数の和 − M1×M2の倍数の和

x の倍数について、n 項分の和は次の公式で求められます。

Sum(X) = (n * (1+n) * X) / 2

この公式をもとに全体の合計を定式化すると、以下のようになります。

sum = ((n/M1) * (1 + (n/M1)) * M1 / 2) + ((n/M2) * (1 + (n/M2)) * M2 / 2) - ((n/(M1*M2)) * (1 + (n/(M1*M2))) * (M1*M2) / 2)

なお、「N 未満」という条件を厳密に扱うため、計算の前に N を 1 減らしておく点に注意してください。

サンプルコード

#include <iostream>
using namespace std;

int calcMulSum(int N, int M1, int M2){
    N--;
    return (((N/M1) * (1 + (N/M1)) * M1 / 2) + ((N/M2) * (1 + (N/M2)) * M2 / 2) - ((N/(M1*M2)) * (1 + (N/(M1*M2))) * (M1*M2) / 2));
}

int main(){
    int N = 24, M1 = 4, M2 = 7;
    cout << "The sum of multiples of " << M1 << " and " << M2 << " below " << N << " is " << calcMulSum(N, M1, M2);
    return 0;
}

実行結果

The sum of multiples of 4 and 7 below 24 is 102

まとめ

ループによる全探索では O(n) の時間計算量が必要ですが、等差数列の和の公式と包除原理を組み合わせれば、ループ処理なしに O(1) で答えを求められます。N が非常に大きな値でも高速に動作するため、実務上は公式ベースのアプローチが推奨されます。