C ++中给定乘积的N个整数的最大GCD
假设我们有两个整数N和P。P是N个未知整数的乘积。我们必须找到这些整数的最大可能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。
我们将找到P的所有素因子，并将它们存储到哈希映射中。当素数因子在所有整数中都相同时，N个整数将具有最大GCD。因此，如果P=p1k1*p2k2*…*pnkn。pi是主要因素。然后最大GCD将RES=P1K1/N*P2K2/N*...*pÑKN/N。
示例
#include <iostream>
#include <cmath>
#include <unordered_map>
using namespace std;
long getMaxGCD(long N, long p) {
int gcd = 1;
unordered_map<int, int> prime_factors;
for (int i = 2; i * i <= p; i++) {
while (p % i == 0) {
prime_factors[i]++;
p /= i;
}
}
if (p != 1)
prime_factors[p]++;
for (auto v : prime_factors)
gcd = gcd * pow(v.first, v.second / N);
return gcd;
}
int main() {
long n = 3;
long p = 24;
cout << "MAX GCD: " << getMaxGCD(n, p);
}输出结果
MAX GCD: 2