C++で指定された製品のN個の整数の最大GCD

2つの整数NとPがあるとします。PはN個の未知の整数の積です。これらの整数の可能な最大GCDを見つける必要があります。 N =3、P =24とすると、異なるグループは{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 ₁の場合 ^k1 * p ₂ ^k2 *…*p _n ^kn 。ここで、piは素因数です。その場合、最大GCDはres =p ₁になります。 ^{k1 / N} * p ₂ ^{k2 / N} *…*p _n ^{kn / N} 。

例

#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]++;
   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