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 dương n và m cho trước. Đây là bài toán kinh điển về thuật toán Euclid. Input gồm hai số n và m, output là một số nguyên - UCLN của chúng.

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

Cách Thuật toán Euclid (Đệ quy)

#include <bits/stdc++.h>

using namespace std;

long long gcd(long long a, long long b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("ucln.inp", "r", stdin);
    freopen("ucln.out", "w", stdout);

    long long n, m; cin >> n >> m;
    cout << gcd(n, m);
}

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

Phương pháp này sử dụng tính chất UCLN(a, b) = UCLN(b, a % b). Hàm gcd được gọi đệ quy cho đến khi số hạng thứ hai bằng 0, lúc đó số hạng đầu tiên chính là UCLN. Đây là cách diễn đạt trực quan nhất của thuật toán Euclid.

Cách Thuật toán Euclid (Vòng lặp)

#include <iostream>
#define ll long long
using namespace std;

ll ucln(ll a, ll b) {
   ll r;
   while (b !=0) {
      r = a % b;
      a = b;
      b = r;
   }
   return a;
}

int main () {
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   freopen("ucln.inp", "r", stdin);
   freopen("UCLN.OUT", "w", stdout);
   long long m, n; cin >> m >> n;
   cout << ucln(m, n) << endl;
   return 0;
}

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

Đây là phiên bản tương tự nhưng sử dụng vòng lặp while thay vì đệ quy. Biến r lưu trữ phần dư, a và b được cập nhật liên tục cho đến khi b bằng 0. Ưu điểm của phương pháp này là tránh nguy cơ tràn bộ nhớ stack (stack overflow) với các input rất lớn, đồng thời hiệu năng thường tốt hơn một chút so với đệ quy.

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

Bài học kinh nghiệm

• Tính chất cơ bản của UCLN: UCLN(a, b) = UCLN(b, a % b).
• Điều kiện dừng: Khi một trong hai số bằng 0, số còn lại chính là UCLN.
• Thời gian chạy của thuật toán Euclid rất nhanh, chỉ cần khoảng O(log N) bước.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu sai (ví dụ: int thay vì long long) dẫn đến tràn số nếu input lớn.
• Quên xử lý trường hợp hai số bằng 0 (nếu đề bài cho phép số 0), mặc dù trong bài này input là số nguyên dương.
• Viết sai điều kiện dừng trong đệ quy (ví dụ: if (a == 0) thay vì kiểm tra b).