C++で配列のGCDを大きくするための最小削除数を求めるアルゴリズム

概要

N個の整数が与えられたとき、残りの数のGCD(最大公約数)が、元のN個の数のGCDよりも大きくなるようにするために取り除くべき数の最小個数を求めます。GCDを大きくすることが不可能な場合は「NO」と出力します。

入力例1

b[] = {1, 2, 4}

出力例1

1

最初の要素「1」を取り除くと、残りの数のGCDは2となり、元のGCD(1)より大きくなります。必要な削除数は1です。

入力例2

b[] = {6, 9, 15, 30}

出力例2

2

元のGCDは3です。6と9の2つを取り除くと、残りは{15, 30}となり、GCDは15になります。これは元のGCDの3より大きいため、必要な削除数は2です。

解法のアプローチ

この問題は、以下の手順に従って解くことができます。

• まず、ユークリッドの互除法を用いてN個の数のGCDを求めます。
• 次に、求めたGCDで配列内のすべての要素を割ります。
• 「最小の素因数(SPF)」を事前に計算しておくことで、各要素の素因数分解をO(log N)で高速に行えます。
• setを用いて素因数を格納し、同じ要素内で重複する素因数を取り除きます。
• ハッシュマップ(unordered_map)を使い、各素因数が何個の要素に出現するかをカウントします。
• すべての要素の素因数分解が完了し、出現頻度表ができたら、ハッシュマップを走査して最も多く出現する素因数を特定します。この素因数の出現回数がNになることはありません。すでに配列の要素を初期GCDで割っているため、すべての要素に共通する素因数は存在しないからです。
• したがって、初期GCDで割った後に何らかの素因数が存在する場合、答えは常に「N − hash[素因数]」となります。

実装例(C++)

// このC++プログラムは、残りの数のGCDが元のN個の数のGCDより
// 大きくなるようにするための最小削除数を求めます
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
// 各数の最小の素因数を格納する配列
int spf1[MAXN];
// MAXNまでのすべての数についてSPF(最小の素因数)を計算します
// 時間計算量: O(n log log n)
void sieve1(){
    spf1[1] = 1;
    for (int i = 2; i < MAXN; i++)
        // まず各数の最小の素因数を自分自身に設定
        spf1[i] = i;
    // 偶数については、別途2をSPFとして設定
    for (int i = 4; i < MAXN; i += 2)
        spf1[i] = 2;
    for (int i = 3; i * i < MAXN; i++) {
        // iが素数かどうかを判定
        if (spf1[i] == i) {
            // iで割り切れるすべての数に対してSPFを設定
            for (int j = i * i; j < MAXN; j += i)
                // まだ設定されていない場合のみspf1[j]を更新
                if (spf1[j] == j)
                    spf1[j] = i;
        }
    }
}
// 毎回最小の素因数で割ることで、
// O(log n)で素因数分解を行う関数
vector<int> getFactorization1(int x){
    vector<int> ret;
    while (x != 1) {
        ret.push_back(spf1[x]);
        x = x / spf1[x];
    }
    return ret;
}
// GCDを元の値より大きくするために
// 必要な最小削除数を返す関数
int minimumRemovals1(int a1[], int n){
    int g = 0;
    // 初期GCDを求める
    for (int i = 0; i < n; i++)
        g = __gcd(a1[i], g);
    unordered_map<int, int> mpp;
    // すべての数を初期GCDで割る
    for (int i = 0; i < n; i++)
        a1[i] = a1[i] / g;
    // すべての数について処理
    for (int i = 0; i < n; i++) {
        // 素因数分解により、配列のi番目の要素の
        // 素因数を取得
        vector<int> p = getFactorization1(a1[i]);
        set<int> s1;
        // すべての素因数をsetに挿入し、重複を除去
        for (int j = 0; j < p.size(); j++) {
            s1.insert(p[j]);
        }
        // 各要素について、素因数の出現回数をマップに加算
        for (auto it = s1.begin(); it != s1.end(); it++) {
            int el = *it;
            mpp[el] += 1;
        }
    }
    int mini = INT_MAX;
    // マップを走査し、各素因数とその出現回数を確認
    for (auto it = mpp.begin(); it != mpp.end(); it++) {
        int fir1 = it->first;
        int sec1 = it->second;
        // 最も多く出現する素因数を特定
        if ((n - sec1) <= mini) {
            mini = n - sec1;
        }
    }
    if (mini != INT_MAX)
        return mini;
    else
        return -1;
}
// ドライバーコード
int main(){
    int a1[] = { 6, 9, 15, 30 };
    int n = sizeof(a1) / sizeof(a1[0]);
    sieve1();
    cout << minimumRemovals1(a1, n);
    return 0;
}

出力

2