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