ค้นหาคู่ใด ๆ ที่มี GCD และ LCM ที่กำหนดใน C++

ในส่วนนี้ เราจะมาดูวิธีรับจำนวนคู่โดยใช้ค่า 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