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 ^그냥 . 여기서 파이는 소인수입니다. 그러면 최대 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