C++에서 주어진 미지수 곱의 최대 GCD

두 개의 정수 N과 P가 있다고 가정합니다. P는 N개의 미지수 정수의 곱입니다. 우리는 그 정수들의 GCD를 찾아야 합니다. 동일한 결과를 제공하는 다른 정수 그룹이 있을 수 있습니다. 여기서 우리는 가능한 모든 그룹 중에서 최대인 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입니다.

우리가 좋아하는 기술, g가 a₁의 GCD라고 가정합니다. , a₂ , ... a_n . 그러면 ai는 g의 배수이고 P는 (a₁ * a₂ * ... * a_n )는 g ⁿ 의 배수여야 합니다. . 답은 g ⁿ 과 같은 최대 g입니다. mod P =0. 이제 P =k1 ^p1 이라고 가정합니다. * k2 ^p1 * ... * kn ^pn . g는 다음과 같은 형식이어야 하며 g를 최대화하려면 p_i를 선택해야 합니다. =p_i / 아니오.

예시

#include <iostream>
#include <cmath>
using namespace std;
long getMaxGCD(long n, long p) {
   int count = 0;
   long gcd = 1;
   while (p % 2 == 0) {
      p >>= 1;
      count++; //number of times P divided by 2
   }
   if (count > 0) //if p has some 2s, then
      gcd = gcd* (long)pow(2, count / n);
   for (long i = 3; i <= sqrt(p); i += 2) { //check for all numbers after 2
      count = 0;
      while (p % i == 0) {
         count++;
         p = p / i;
      }
      if (count > 0) {
         gcd = gcd* (long)pow(i, count / n);
      }
   }
   // If n in the end is a prime number
   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