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 ₂，…a _n的GCD 。那么ai是g的倍数，而P是（a ₁ * a ₂ *…* a _n）必须是g ⁿ的倍数。答案是max g，使得g ⁿ mod P =0。现在假设P = k1 ^p1 * k2 ^p1 *…* kn ^pn。g必须是这样的形式，然后要最大化g，我们必须选择p _i = p _i / N。

示例

#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);
      }
   }
   //如果最后的n是质数
   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