หาคู่ใดคู่หนึ่งจาก 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){ //ถ้า n หาร 2 ลงตัว   count++;   while(n%2 == 0)   n = n/2;   }   //ตอนนี้ n เป็นคี่ ถ้าเพิ่ม i ทีละ 2 จะได้เลขคี่ทั้งหมด   for(int i = 3; i*i <= n; i = i + 2){     if(n%i == 0){     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