資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究在 C++ 中找到任意一對具有給定 GCD 和 LCM 的數
在本節中，我們將看到如何使用給定的 GCD 和 LCM 值獲取對的數量。假設 GCD 和 LCM 值為 2 和 12。那麼可能的數字對為 (2, 12)、(4, 6)、(6, 4) 和 (12, 2)。因此，我們的程式將找到這些對的數量。即 4。
讓我們看看演算法來了解解決這個問題的技術是什麼。
演算法
countPairs(gcd, lcm): Begin if lcm is nit divisible by gcd, then return 0 temp := lcm/gcd c := primeFactorCount(temp) res := shift 1 to the left c number of times return res End primeFactorCount(n): Begin count := 0 until n is not odd, increase count and divide n by 2 for i := 3, when i2 < n, increase i by 2, do if n is divisible by i, then increase count while n is divisible by i, do n := n / i done end if done if n > 2, then increase count by 1 return count End
示例
#include<iostream>
#include<cmath>
using namespace std;
int primeFactorCount(int);
int countPairs(int gcd, int lcm) {
if(lcm % gcd != 0)
return 0;
int temp = lcm/gcd;
return (1 << primeFactorCount(temp));
}
int primeFactorCount(int n){
int count = 0;
if(n%2 == 0){ //if n is divisible by 0, enter into the next part
count++;
while(n%2 == 0)
n = n/2;
}
//now n is odd, so if we increase n by 2, all numbers will be odd
for(int i = 3; i*i <= n; i = i + 2){
if(n%i == 0){ //if n is divisible by 0, enter into the next part
count++;
while(n%i == 0)
n = n/i;
}
}
if(n > 2)
count++;
return count;
}
int main() {
cout << "Possible pairs of GCD = 2, and LCM = 12 is " <<countPairs(2, 12);
}輸出
Possible pairs of GCD = 2, and LCM = 12 is 4
更新於： 25-9-2019
210 次瀏覽
廣告