数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中未知数乘积中的最大公约数
假设我们有两个整数 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。
这种技术如下所示，假设 g 是 a1、a2、… an 的最大公约数。则 ai 是 g 的倍数，而 P 是 (a1 * a2 * … * an) 一定要 gn 的倍数。答案是使得 gn mod P = 0 的最大 g。现在假设 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);
}
}
// If n in the end is a prime number
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
更新时间：2019 年 10 月 21 日
105 次浏览
广告