Tìm bất kỳ cặp nào với GCD và LCM đã cho trong C ++

Trong phần này, chúng ta sẽ xem cách lấy số cặp bằng cách sử dụng các giá trị GCD và LCM đã cho. Giả sử giá trị GCD và LCM là 2 và 12. Bây giờ các cặp số có thể có là (2, 12), (4, 6), (6, 4) và (12, 2). Vì vậy, chương trình của chúng tôi sẽ tìm số lượng các cặp. Đó là 4.

Hãy cùng chúng tôi xem thuật toán để hiểu đâu sẽ là kỹ thuật giải quyết vấn đề này.

Thuật toán

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

Ví dụ

#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);
}

Đầu ra

Possible pairs of GCD = 2, and LCM = 12 is 4