C++での未知数の特定の製品からの最大GCD

2つの整数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 /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);
      }
   }
   // 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