【C++】配列内のちょうど1つの要素を除くすべての要素の約数となる整数の求め方

概念

整数の配列が与えられたとき、配列内のちょうど1つの要素を除くすべての要素の約数となる整数を求めることが課題です。

なお、この問題ではすべての要素の最大公約数（GCD）は1ではないものとします。これは、条件を満たす整数が必ず存在することを保証するための前提条件です。

入力例1

arr[] = {8, 16, 4, 24}

出力例1

8
8 は 4 を除くすべての要素の約数です。

入力例2

arr[] = {50, 15, 40, 41}

出力例2

5
5 は 41 を除くすべての要素の約数です。

解法のアプローチ

まず、プレフィックス配列 A を作成します。A の位置 i には「先頭から i 番目までの要素のGCD」を格納します。同様に、サフィックス配列 C を作成し、C の位置 i には「i 番目から末尾（n-1 番目）までの要素のGCD」を格納します。

次に、A[i-1] と C[i+1] のGCDを計算します。この値が i 番目の要素を割り切れない場合、それこそが求める答えです。「i 番目以外のすべての要素」のGCDが i 番目の要素の約数にならないならば、そのGCDは「ちょうど1つの要素を除くすべての要素の約数」という条件を満たすためです。

計算量は要素数を n、要素の最大値を M とすると時間 O(n log M)、必要なメモリは O(n) となり、非常に効率的です。

動作の確認（arr[] = {50, 15, 40, 41} の場合）

• プレフィックス配列 A = {50, 5, 5, 1}
• サフィックス配列 C = {1, 1, 40, 41}
• i = 3（要素 41）のとき：cur = gcd(A[2], C[4]) = gcd(5, 41) = 5。41 % 5 ≠ 0 なので、答えは 5 となります。

C++による実装例

// 配列内のちょうど1つの要素を除く
// すべての要素の約数を求めるC++プログラム
#include <bits/stdc++.h>
using namespace std;

// ちょうど1つの要素を除くすべての要素の約数を返す関数
int getDivisor1(int a1[], int n1){
    // 配列の要素が1つしかない場合
    if (n1 == 1)
        return (a1[0] + 1);
    int A[n1], C[n1];
    // GCDのプレフィックス（前方累積）配列を作成
    A[0] = a1[0];
    for (int i = 1; i < n1; i++)
        A[i] = __gcd(a1[i], A[i - 1]);
    // GCDのサフィックス（後方累積）配列を作成
    C[n1-1] = a1[n1-1];
    for (int i = n1 - 2; i >= 0; i--)
        C[i] = __gcd(C[i + 1], a1[i]);
    // 配列を走査する
    for (int i = 0; i < n1; i++) {
        // 約数を格納する変数
        int cur1;
        // 候補となる約数を取得
        if (i == 0)
            cur1 = C[i + 1];
        else if (i == n1 - 1)
            cur1 = A[i - 1];
        else
            cur1 = __gcd(A[i - 1], C[i + 1]);
        // a1[i] の約数でなければ答えとして返す
        if (a1[i] % cur1 != 0)
            return cur1;
    }
    return 0;
}

// ドライバーコード
int main(){
    int a1[] = { 50,15,40,41 };
    int n1 = sizeof(a1) / sizeof(a1[0]);
    cout << getDivisor1(a1, n1);
    return 0;
}

出力

5