C++で繰り返し減算により全要素を等しくした後の最大配列合計を求める方法

n個の要素からなる配列が与えられたとします。このとき、すべての要素を同じ値にした状態での、要素の合計の最大値を求めることを考えます。ただし、許されている操作は「任意の2つの要素を選び、大きい方の値を2つの差（絶対値）で置き換える」というものだけです。

例として、配列が [9, 12, 3, 6] の場合を考えてみましょう。この場合の出力は 12 になります。

手順の例

1. A[1] を A[1] − A[3] = 12 − 6 = 6 に置き換えます。→ 配列は [9, 6, 3, 6]
2. A[3] を A[3] − A[2] = 6 − 3 = 3 に置き換えます。→ 配列は [9, 6, 3, 3]
3. A[0] を A[0] − A[1] = 9 − 6 = 3 に置き換えます。→ 配列は [3, 6, 3, 3]
4. A[1] を A[1] − A[3] = 6 − 3 = 3 に置き換えます。→ 配列は [3, 3, 3, 3]

これですべての要素が 3 になり、合計は 3 × 4 = 12 となります。

アルゴリズムのポイント

この操作を分析すると、A[i] > A[j] のときに A[i] = A[i] − A[j] という置き換えを行っていることがわかります。これはまさにユークリッドの互除法と同じ仕組みです。したがって、この操作を繰り返すと、最終的にすべての要素は配列全体の最大公約数（GCD）に収束します。

つまり、答えは「配列全体のGCD × 要素数 n」で求められます。

C++による実装例

#include<iostream>
#include<algorithm>
using namespace std;

// 配列全体のGCDを求める関数
int findSameElement(int arr[], int n) {
    int gcd_val = arr[0];
    for (int i = 1; i < n; i++)
        gcd_val = __gcd(arr[i], gcd_val);
    return gcd_val;
}

// 最大合計を計算する関数
int getMaxSum(int arr[], int n) {
    int value = findSameElement(arr, n);
    return (value * n);
}

int main() {
    int arr[] = {3, 9, 6, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "The maximum sum is: " << getMaxSum(arr, n);
}

実行結果

The maximum sum is: 12

まとめ

この問題は一見複雑なシミュレーションが必要に思えますが、「繰り返し減算による要素の置き換え」がユークリッドの互除法と本質的に同じであることに気づくことが鍵となります。配列全体のGCDを求め、それに要素数を掛けるだけで O(n log(max(A))) の効率的な計算で答えが得られます。