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