Hiểu bài toán

Bài toán yêu cầu kiểm tra xem hai số nguyên dương a và b có phải là cặp số nguyên tố cùng nhau (coprime) hay không. Hai số được gọi là nguyên tố cùng nhau nếu ước số chung lớn nhất (GCD) của chúng bằng 1. Input gồm hai số a, b, output là 'YES' nếu chúng nguyên tố cùng nhau, ngược lại输出 'NO'.

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

Cách Sử dụng hàm có sẵn (__gcd)

#include <bits/stdc++.h>
using namespace std;
int main() {
    freopen("COPRIME.INP", "r", stdin);
    freopen("COPRIME.OUT", "w", stdout);
    long long a, b; cin >> a >> b;
    if (__gcd(a, b) == 1) cout << "YES";
    else cout << "NO";
}

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

Đây là cách tiếp cận trực tiếp nhất. Hàm __gcd(a, b) trong thư viện <algorithm> hoặc <numeric> (tùy phiên bản C++) sử dụng thuật toán Euclid để tính ước chung lớn nhất. Độ phức tạp logarithmic. Cần lưu ý về việc khai báo kiểu dữ liệu (long long) nếu số lớn và mở file input/output đúng cách.

Cách Thuật toán Euclid (tự cài đặt)

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    freopen("COPRIME.INP", "r", stdin);
    freopen("COPRIME.OUT", "w", stdout);
    long long a, b;
    cin >> a >> b;
    if (gcd(a, b) == 1) cout << "YES";
    else cout << "NO";
    return 0;
}

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

Nếu không muốn dựa vào hàm có sẵn, ta có thể tự cài đặt thuật toán Euclid. Thuật toán này dựa trên nguyên lý GCD(a, b) = GCD(b, a % b). Nó lặp lại quá trình này cho đến khi số thứ hai bằng 0. Đây là nền tảng cho cách tiếp cận đầu tiên.

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

Bài học kinh nghiệm

• Hai số nguyên dương nguyên tố cùng nhau khi và chỉ khi GCD của chúng bằng 1.
• Thuật toán Euclid là phương pháp hiệu quả nhất để tính GCD với độ phức tạp O(log(min(a, b))).

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int thay vì long long có thể gây tràn số (overflow) nếu a hoặc b lớn hơn 2*10^9.
• Quên mở file input/output (freopen) hoặc sai tên file会导致 bài toán không đọc được dữ liệu hoặc không ghi được kết quả.