資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告