C++でN個の未知整数の積Pから最大GCDを求めるアルゴリズム

2つの整数 N と P が与えられ、P が N 個の未知の整数の積であるとします。このとき、これらの整数のGCD（最大公約数）を求める必要があります。ただし、同じ積 P になる整数の組み合わせは複数存在し得るため、その中で最も大きなGCDを求めることが目標です。

例として、N = 3、P = 24 の場合を考えてみましょう。積が24になる3つの整数の組み合わせには {1, 1, 24}、{1, 2, 12}、{1, 3, 8}、{1, 4, 6}、{2, 2, 6}、{2, 3, 4} などがあり、それぞれのGCDは 1, 1, 1, 1, 2, 1 となります。したがって、この場合の答えは 2 です。

解法の考え方

g が a₁, a₂, …, a_n のGCDであると仮定します。すると、各 a_i は g の倍数であるため、積 P = (a₁ × a₂ × … × a_n) は必ず gⁿ の倍数になります。つまり、答えは「gⁿ が P を割り切るような最大の g」です。

ここで、P を素因数分解して P = k₁^p1 × k₂^p2 × … × k_m^pm と表せるものとします。g も同様の形で表現できるため、g を最大化するには、各素因数の指数について p_i / N（整数除算）を採用すればよいことになります。

C++による実装例

#include <iostream>
#include <cmath>
using namespace std;
long getMaxGCD(long n, long p) {
    int count = 0;
    long gcd = 1;
    // まず素因数2の指数を数える
    while (p % 2 == 0) {
        p >>= 1;
        count++; // Pを2で割った回数
    }
    if (count > 0) // 2の因数を持つ場合
        gcd = gcd * (long)pow(2, count / n);
    // 3以降の奇数について調べる
    for (long i = 3; i <= sqrt(p); i += 2) {
        count = 0;
        while (p % i == 0) {
            count++;
            p = p / i;
        }
        if (count > 0) {
            gcd = gcd * (long)pow(i, count / n);
        }
    }
    // 最後に残った数が素数の場合
    if (p > 2)
        gcd = gcd * (long)pow(p, 1 / n);
    return gcd;
}
int main() {
    long n = 3;
    long p = 24;
    cout << "MAX GCD: " << getMaxGCD(n, p);
}

実行結果

MAX GCD: 2

コードのポイント

• 最初に素因数 2 をビットシフト（p >>= 1）で効率的に除去し、その出現回数をカウントします。
• 続いて、3以上の奇数を √P まで順に試し割りし、各素因数の指数を求めます。
• 各素因数について「指数 ÷ N」（整数除算）を累乗した値をGCDに掛け合わせていくことで、条件を満たす最大のGCDが得られます。
• ループ終了後に残った p が2より大きければ、それは素因数として扱います。

このアルゴリズムは素因数分解に基づいているため、P が大きくても試し割り法により O(√P) の計算量で効率的に答えを求められます。