Hiểu bài toán

Bài toán yêu cầu tìm ước chung lớn nhất (UCLN) của hai số nguyên a và b. Dữ liệu đầu vào có thể là số âm, số dương hoặc 0 (nhưng không cả hai cùng bằng 0). UCLN được định nghĩa là số nguyên dương lớn nhất chia hết cho cả a và b. Ví dụ: UCLN(2, 4) = 2, UCLN(-2, -10) = 2, UCLN(0, 43) = 43.

Các cách tiếp cận

Cách Brute Force (Duyệt vòng lặp)

#include <stdio.h>

int ucln(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;

    if (a == 0 && b == 0) {
        return 0; 
    }
    if (a==0 && b!=0) {
        return b;
    }
    if (a!=0 && b==0) {
        return a;
    }

    int max = 1;
    for (int i = 1; i <= a && i <= b; i++) {
        if (a % i == 0 && b % i == 0) {
            max = i;
        }
    }

    return max;
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);

    printf("%d", ucln(a, b));
    return 0;
}

• Time Complexity: O(min(|a|, |b|))
• Space Complexity: O(1)

Phương pháp này dùng vòng lặp từ 1 đến min(a, b) để tìm số lớn nhất chia hết cho cả hai số a và b. Nó kiểm tra từng số xem có phải là ước chung không và cập nhật giá trị lớn nhất. Cách này đơn giản để hiểu nhưng chậm với số lớn.

Cách Thuật toán Euclid

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int a, b, r;
    scanf("%d %d", &a, &b);
    a = abs(a);
    b = abs(b);
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    printf("%d", a);
    return 0;
}

• Time Complexity: O(log(min(|a|, |b|)))
• Space Complexity: O(1)

Thuật toán Euclid dựa trên nguyên lý UCLN(a, b) = UCLN(b, a % b). Vòng lặp tiếp tục cho đến khi số hạng thứ hai bằng 0. Đây là phương pháp chuẩn và hiệu quả để tính UCLN, có độ phức tạp logarithmic.

Cách Thuật toán Euclid (Bản mẫu khác)

#include <stdio.h>
#include <math.h>

int main(){
    int a, b;
    scanf("%d%d", &a, &b);
    a = abs(a);
    b = abs(b);
    if (a == 0) {
        printf("%d", b);
        return 0;
    }
    if (b == 0) {
        printf("%d", a);
        return 0;
    }
    int c;
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    printf("%d\n", a);
    return 0;
}

• Time Complexity: O(log(min(|a|, |b|)))
• Space Complexity: O(1)

Đây là một cách triển khai khác của thuật toán Euclid, tương tự như cách trên. Nó xử lý các trường hợp đầu vào đặc biệt (a hoặc b bằng 0) ở ngoài vòng lặp.

Phân tích độ phức tạp

Bài học kinh nghiệm

• UCLN(a, b) = UCLN(|a|, |b|), nên có thể đưa các số về dương để xử lý dễ dàng hơn.
• Thuật toán Euclid là cách hiệu quả nhất để giải quyết bài này với độ phức tạp logarithmic.

Lỗi thường gặp

• Quên xử lý trường hợp số âm (cần lấy giá trị tuyệt đối).
• Vòng lặp duyệt brute force có thể chạy quá lâu nếu số lớn (ví dụ 10000), gây TLE trong các bài toán phức tạp hơn.