C++で要素の積とLCMが一致する最長部分配列を求めるアルゴリズム

問題概要

配列 A が与えられたとき、「その部分配列の最小公倍数（LCM）」と「部分配列内の要素の積」が一致するような部分配列の中で、最も長いものの長さを求めます。条件を満たす部分配列が存在しない場合は -1 を返します。

例として、配列が {6, 10, 21} である場合を考えてみましょう。部分配列 {10, 21} に注目すると、その最小公倍数は 210、要素の積も 210 となり、両者が一致します。このため、答えは 2 となります。

解き方のアプローチ

この問題へのアプローチは非常にシンプルです。長さ 2 以上のすべての部分配列を網羅的にチェックし、条件を満たすものが見つかるたびに、これまでの答えと部分配列の長さを比較して、より大きい方で答えを更新していきます。

• 開始位置 i と終了位置 j を二重ループで全通り試す（部分配列の長さは必ず 2 以上になるようにする）。
• 各区間 [i, j] の要素を順番に処理しながら、最小公倍数と積を累積的に計算する。
• 最小公倍数と積が一致した場合、len = max(len, 部分配列の長さ) として答えを更新する。

なお、2つの整数 a, b の最小公倍数は「Lcm(a, b) = (a × b) / Gcd(a, b)」という関係式を使えば、最大公約数（GCD）を経由して簡単に求められます。また、積の値が急激に大きくなりやすいことを考慮し、オーバーフロー対策として long long 型を使用している点にも注目してください。

C++での実装例

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int maxLengthLCMSubarray(int arr[], int n) {
    int len = -1;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            long long lcm = 1LL * arr[i];
            long long product = 1LL * arr[i];
            for (int k = i + 1; k <= j; k++) {
                lcm = (((arr[k] * lcm)) / (gcd(arr[k], lcm)));
                product = product * arr[k];
            }
            if (lcm == product) {
                len = max(len, j - i + 1);
            }
        }
    }
    return len;
}

int main() {
    int arr[] = {8, 2, 6, 10, 13, 21, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum Length: " << maxLengthLCMSubarray(arr, n);
}

出力結果

Maximum Length: 3

入力配列 {8, 2, 6, 10, 13, 21, 7} の場合、部分配列 {10, 13, 21} に注目すると、その最小公倍数は 2730、要素の積も 2730 となり一致します。これより長い条件を満たす部分配列は存在しないため、答えは 3 になります。

補足：計算量と数学的な性質

この実装は三重のループを用いているため、計算量は概ね O(n³) となり、n が比較的小さい場合に適した手法です。

さらに数学的な観点から見ると、「複数の数全体の最小公倍数が積と一致する」のは「どの2つの要素も互いに素である」とき、かつそのときに限られます。この性質を利用すれば、隣接する要素同士の互除性判定に問題を言い換えることができ、計算量を O(n²) まで改善できる可能性があります。競技プログラミングなどで大きな入力を扱う際には、ぜひこの点も検討してみてください。