Giả sử chúng ta có hai số nguyên N và P. P là tích của N số nguyên chưa biết. Chúng ta phải tìm GCD tối đa có thể có của những số nguyên đó. Giả sử N =3 và P =24, thì các nhóm khác nhau sẽ giống như {1, 1, 24}, {1, 2, 12}, {1, 3, 8}, {1, 4, 6}, {2 , 2, 6}, {2, 3, 4}. GCD là:1, 1, 1, 1, 2, 1. Vậy câu trả lời là 2 ở đây.
Chúng ta sẽ tìm tất cả các thừa số nguyên tố của P và lưu trữ chúng vào bản đồ băm. N số nguyên sẽ có GCD tối đa khi thừa số nguyên tố là chung trong tất cả các số nguyên. Vì vậy, nếu P =p 1 k1 * p 2 k2 *… * P n kn . Ở đây pi là thừa số nguyên tố. Khi đó GCD tối đa sẽ là res =p 1 k1 / N * p 2 k2 / N *… * P n kn / N .
Ví dụ
#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);
} Đầu ra
MAX GCD: 2