数据结构
网络
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 次浏览
广告