資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚學
法律學C++ 中給定乘積求 N 個整數的最大 GCD
假設有兩個整數 N 和 P。P 是 N 個未知整數的乘積。我們必須求出這些整數的最大可能公約數。假設 N = 3，且 P = 24，那麼不同的分組形式有：{1, 1, 24}、{1, 2, 12}、{1, 3, 8}、{1, 4, 6}、{2, 2, 6}、{2, 3, 4}。公約數為：1、1、1、1、2、1。因此，這裡的答案是 2。
我們將找到 P 的所有素因子，並將它們儲存到雜湊表中。如果所有整數中都存在公有素因子，則 N 個整數的最大公約數將最大。所以，如果 P = p1k1 * p2k2 * … * pnkn。這裡的 pi 是素因子。那麼，最大公約數將是 res = p1k1/N * p2k2/N * … * pnkn/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
更新於: 2019-10-21
130 次瀏覽
廣告