C ++中给定乘积的N个整数的最大GCD

假设我们有两个整数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 _Ñ ^{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