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
热门推荐
10 祝女儿简短祝福语大全
11 大学新年祝福语简短创意
12 元旦适合的祝福语简短
13 朋友出远门祝福语简短
14 初六简短的祝福语
15 祝男孩生日祝福语简短
16 同事调离的祝福语简短
17 拜年红包的祝福语简短
18 妈妈生日祝福语简短励志