用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;
}
//现在n是奇数，所以如果我们将n加2，所有数字都将是奇数
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