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是1，a2，…an的GCD。那么ai是g的倍数，而P是（a1*a2*…*an）必须是gn的倍数。答案是maxg，使得gnmodP=0。现在假设P=k1p1*k2p1*…*knpn。g必须是这样的形式，然后要最大化g，我们必须选择pi=pi/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