C++で積がPとなるN個の整数の最大GCDを求める方法

2つの整数 N と P が与えられているとします。P は N 個の未知の整数の積であり、そのときそれらの整数の最大公約数（GCD）としてあり得る最大値を求めるのが課題です。

例として、N = 3、P = 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 です。

解法のアプローチ

まず P のすべての素因数を求め、ハッシュマップに格納します。各素因数が N 個の整数すべてに共通して含まれるとき、GCDは最大になります。

P を次のように素因数分解できるとします。

P = p₁^k1 × p₂^k2 × … × p_n^kn（ここで p_i は素因数）

このとき、最大GCDは次の式で求められます。

res = p₁^k1/N × p₂^k2/N × … × p_n^kn/N

つまり、各素因数の指数を N で割った値を累乗として掛け合わせることで、すべての整数に均等に分配できる素因数の分だけGCDを最大化できます。

C++での実装例

#include <iostream>
#include <cmath>
#include <unordered_map>
using namespace std;

long getMaxGCD(long N, long p) {
    int gcd = 1;
    unordered_map<int, int> prime_factors;

    // 素因数分解を行い、指数を記録する
    for (int i = 2; i * i <= p; i++) {
        while (p % i == 0) {
            prime_factors[i]++;
            p /= i;
        }
    }
    if (p != 1)
        prime_factors[p]++;

    // 各素因数の指数をNで割った値を掛け合わせる
    for (auto v : prime_factors)
        gcd = gcd * pow(v.first, v.second / N);

    return gcd;
}

int main() {
    long n = 3;
    long p = 24;
    cout << "MAX GCD: " << getMaxGCD(n, p);
}

出力結果

MAX GCD: 2

このアルゴリズムの計算量は、素因数分解部分が O(√P)、集計部分が O(素因数の種類数) となるため、P が大きくなっても効率的に動作します。