Hiểu bài toán

Bài toán yêu cầu tìm bội chung nhỏ nhất (BCNN) của hai số nguyên a và b. BCNN là số nguyên dương nhỏ nhất mà chia hết cho cả a và b. Dữ liệu đầu vào gồm hai số nguyên a, b, có thể âm hoặc dương, nhưng không đồng thời bằng 0 (a * b ≠ 0). Với các số âm, ta cần tìm BCNN của các giá trị tuyệt đối của chúng.

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

Cách Brute Force (Tìm kiếm tuần tự)

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

int main(){
int a, b;
scanf("%d%d", &a, &b);
int bcnn=0;
for(int i=1;;i++){
    if(i%a==0 && i%b==0){
        bcnn=i;
        break;
    }
}
printf("%d", bcnn);
return 0;
}

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

Phương pháp này thử các số nguyên dương i tăng dần từ 1, và kiểm tra xem i có chia hết cho cả a và b không. Số đầu tiên tìm được chính là BCNN. Tuy nhiên, đoạn mã này có lỗi logic nghiêm trọng: nó chỉ kiểm tra i % a == 0 và i % b == 0. Nếu a hoặc b dương, nó hoạt động tốt. Nhưng nếu a hoặc b âm, phép tính i % a sẽ cho kết quả khác so với phép chia hết về mặt toán học (ví dụ: 3 % (-1) = 0, nhưng 3 % (-2) = -1). Để đúng, cần phải dùng giá trị tuyệt đối của a và b trong điều kiện vòng lặp. Ví dụ: abs(i) % abs(a) == 0. Ngoài ra, nếu a hoặc b bằng 1, vòng lặp sẽ chạy đến số rất lớn trước khi tìm được BCNN (nếu không dùng break đúng cách).

Cách Công thức qua UCLN (Thuật toán Euclid)

#include <stdio.h>
#include <math.h> 
int ucln(int a, int b){
    a=abs(a);
    b=abs(b);
    while(b!=0){
        int c=a%b;
        a=b;
        b=c; 
    } return abs(a); 
} 
int main(){
    int a,b;
    scanf("%d %d", &a,&b);
    if(a!=0 && b!=0){
        printf("%d", abs(a*b)/ucln(a,b));
    } 
}

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

Đây là phương pháp tối ưu và chuẩn nhất dựa trên định lý: BCNN(a, b) * UCLN(a, b) = |a * b|. Bước 1: Tính UCLN của hai số bằng thuật toán Euclid (lặp). Hàm ucln lấy số dư lặp lại cho đến khi một số bằng 0. Bước 2: Tính BCNN bằng cách lấy giá trị tuyệt đối tích của hai số chia cho UCLN. Lưu ý: Do a và b có thể âm, ta phải dùng abs() (giá trị tuyệt đối) cho chúng khi tính UCLN và khi in kết quả.

Cách Brute Force với UCLN (Tối ưu)

#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) return b;
    if (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);
    int d = ucln(a, b);
    int bcnn = (a / d) * b;
    if (bcnn < 0) bcnn = -bcnn;
    printf("%d", bcnn);
    return 0;
}

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

Phương pháp này là sự kết hợp giữa hai bước. Bước đầu tiên là tìm UCLN bằng cách duyệt từ 1 đến min(|a|, |b|). Bước thứ hai là dùng công thức BCNN = (a * b) / UCLN để tính kết quả. So với phương pháp Brute Force 'thuần', cách này nhanh hơn một chút vì nó chỉ duyệt đến UCLN thay vì duyệt đến BCNN (vốn thường lớn hơn UCLN rất nhiều). Tuy nhiên, nó vẫn chậm hơn thuật toán Euclid vì độ phức tạp tìm UCLN là O(N).

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

Bài học kinh nghiệm

• Quan hệ giữa UCLN và BCNN: BCNN(a, b) = |a * b| / UCLN(a, b). Đây là cách hiệu quả nhất để tính BCNN khi đã biết UCLN.
• Xử lý số âm: Với các số nguyên âm, BCNN của chúng bằng BCNN của các số dương tương ứng. Do đó, luôn dùng hàm abs() để đưa về số dương trước khi tính toán.
• Thuật toán Euclid: Đây là thuật toán chuẩn để tính UCLN với độ phức tạp logarithmic, hiệu quả hơn rất nhiều so với duyệt tuần tự.

Lỗi thường gặp

• Lỗi số âm trong vòng lặp: Khi kiểm tra chia hết cho số âm (ví dụ i % a với a < 0), kết quả phép lấy dư ở C/C++ có thể âm hoặc dương tùy hệ thống, gây lỗi logic. Luôn dùng số tuyệt đối abs(a) trong điều kiện chia hết.
• Tràn số (Integer Overflow): Khi tính a * b nếu a và b lớn, kết quả có thể vượt quá giới hạn của kiểu int. Tuy nhiên, trong bài toán này, a, b <= 1000 nên a * b tối đa là 1,000,000, an toàn cho int (2,147,483,647). Nếu dải input lớn hơn, cần dùng long long hoặc tính theo cách (a / UCLN) * b.
• Trường hợp số 0: Đề bài cam kết a * b ≠ 0, nên ta không cần xử lý trường hợp cả hai số cùng bằng 0, nhưng code vẫn nên kiểm tra a=0 hoặc b=0 nếu muốn an toàn.