Tìm cặp số bất kỳ với GCD và LCM cho trước trong C++

Phần này hướng dẫn tìm số lượng cặp số từ GCD và LCM cho trước. Ví dụ GCD=2, LCM=12. Các cặp có thể: (2,12), (4,6), (6,4), (12,2). Chương trình sẽ đếm số cặp, kết quả là 4.

Thuật toán

demCacCap(gcd, lcm):
    Bắt đầu
        nếu lcm không chia hết cho gcd, thì
            trả về 0
        temp := lcm/gcd
        c := demSoNguyenTo(temp)
        res := dịch 1 sang trái c lần
        trả về res
    Kết thúc

demSoNguyenTo(n):
    Bắt đầu
        count := 0
        cho đến khi n không còn chẵn, tăng count và chia n cho 2
        cho i := 3, khi i² <= n, tăng i 2 đơn vị, làm
            nếu n chia hết cho i, thì
                tăng count
                trong khi n chia hết cho i, làm
                    n := n / i
                kết thúc
            kết thúc nếu
        kết thúc
        nếu n > 2, thì
            tăng count 1
        trả về count
    Kết thúc

Ví dụ mã C++

#include<iostream>
#include<cmath>
using namespace std;

int demSoNguyenTo(int);
int demCacCap(int gcd, int lcm) {
    if(lcm % gcd != 0)
        return 0;
    int temp = lcm/gcd;
    return (1 << demSoNguyenTo(temp));
}

int demSoNguyenTo(int n){
    int count = 0;
    if(n%2 == 0){
        count++;
        while(n%2 == 0)
            n = n/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 << "Số cặp có thể với GCD = 2, LCM = 12 là " << demCacCap(2, 12);
}

Kết quả đầu ra

Số cặp có thể với GCD = 2, LCM = 12 là 4