Chương trình C++ đếm ước số chung của hai số

Đếm số lượng ước số chung (common divisors) của hai số a, b. Không cần liệt kê, chỉ đếm.

Quan sát quan trọng

Ước chung của a và b chính là ước của gcd(a, b). Do đó: đếm ước của gcd(a, b).

Thuật toán

countCommonDivisors(a, b):
    g = gcd(a, b)
    count = 0
    for i = 1 to sqrt(g):
        if g % i == 0:
            if g / i == i: count += 1  // i*i = g (chính phương)
            else: count += 2          // cặp (i, g/i)
    return count
end

Code ví dụ

#include <iostream>
#include <cmath>
#include <numeric> // std::gcd C++17
using namespace std;

int gcd(int a, int b) {
    if (a == 0) return b;
    return gcd(b % a, a);
}

int countCommonDivisors(int a, int b) {
    int g = gcd(a, b); // hoặc std::gcd(a,b) C++17
    int count = 0;
    
    for(int i = 1; i * i <= g; i++) {
        if (g % i == 0) {
            if (i == g / i) count += 1;
            else count += 2;
        }
    }
    return count;
}

int main() {
    int a = 12, b = 24;
    cout << "So uoc chung cua " << a << " va " << b << ": " 
         << countCommonDivisors(a, b) << endl;
    
    // Liệt kê để kiểm tra
    int g = gcd(a, b);
    cout << "Uoc chung: ";
    for(int i = 1; i <= g; i++)
        if (g % i == 0) cout << i << " ";
    return 0;
}

Kết quả

So uoc chung cua 12 va 24: 6
Uoc chung: 1 2 3 4 6 12

⚠️ Sửa lỗi output gốc

Output gốc in "The differences array: 6 5 10 1" - hoàn toàn sai context. Đã sửa thành output đúng.

Độ phức tạp

• GCD: O(log min(a,b))
• Đếm ước: O(√g) với g = gcd(a,b)
• Tổng: O(log min(a,b) + √gcd(a,b)) - rất nhanh.

Mở rộng: Liệt kê ước chung

vector<int> getCommonDivisors(int a, int b) {
    int g = gcd(a, b);
    vector<int> divisors;
    for(int i = 1; i * i <= g; i++) {
        if (g % i == 0) {
            divisors.push_back(i);
            if (i != g / i) divisors.push_back(g / i);
        }
    }
    sort(divisors.begin(), divisors.end());
    return divisors;
}