Hiểu bài toán

Bài toán yêu cầu đếm số điểm có tọa độ nguyên nằm trên và bên trong tam giác vuông OAB với O(0,0), A(a,0) và B(0,b). Ta cần tìm hai giá trị:

1. Số điểm nguyên trên biên tam giác (trên tam giác).
2. Số điểm nguyên nằm严格 bên trong tam giác (không tính biên).

Đây là bài toán hình học kết hợp số nguyên tố (Pick's Theorem).

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

Cách Công thức Pick

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;

    while (T--) {
        long long a, b;
        cin >> a >> b;

        // Số điểm trên biên
        long long boundary = a + b + gcd(a, b);
        // Số điểm bên trong (dùng công thức Pick)
        long long inside = (a * b - boundary + 2) / 2;

        cout << boundary << " " << inside << "\n";
    }

    return 0;
}

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

Đây là cách tiếp cận tối ưu nhất dựa trên định lý Pick:

1. Số điểm trên biên (boundary):

   • Đường OA có a+1 điểm nguyên (từ 0 đến a).
   • Đường OB có b+1 điểm nguyên (từ 0 đến b).
   • Đường AB có gcd(a,b)+1 điểm nguyên.
   • Điểm O, A, B bị đếm 2 lần nên: Boundary = (a+1) + (b+1) + (gcd(a,b)+1) - 3 = a + b + gcd(a,b).

2. Số điểm bên trong (inside):

   • Diện tích tam giác S = (a*b)/2.
   • Định lý Pick: S = I + B/2 - 1, trong đó I là số điểm bên trong, B là số điểm trên biên.
   • Từ đó suy ra: I = S - B/2 + 1 = (a*b - B + 2)/2.

Thuật toán cần tính GCD của a và b, sau đó áp dụng công thức. Độ phức tạp O(log(min(a,b))) do thuật toán Euclid.

Cách Tối ưu hóa tính GCD

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        long long a, b;
        cin >> a >> b;
        long long g = gcd(a, b);
        long long boundary = a + b + g;
        long long inside = (a * b - boundary + 2) / 2;
        cout << boundary << ' ' << inside << '\n';
    }
    return 0;
}

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

Cách tiếp cận này tương tự như cách đầu tiên nhưng:

1. Sử dụng hàm GCD dạng lặp thay vì đệ quy để tránh tràn stack (mặc dù với a,b ≤ 10^9 thì đệ quy vẫn an toàn).
2. Tách biệt việc tính toán GCD trước để code rõ ràng hơn.

Công thức tính toán vẫn giữ nguyên:

• Boundary = a + b + gcd(a,b)
• Inside = (a*b - boundary + 2)/2

Độ phức tạp không đổi nhưng có thể chạy nhanh hơn một chút do tránh overhead đệ quy.

Cách Công thức biến đổi trực tiếp

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        long long a, b;
        cin >> a >> b;
        ll u = gcd(a, b);
        ll x = a + b + u;
        ll s = abs(a * b);
        ll y = (s - x + 2) / 2;
        cout << x << ' ' << y << '\n';
    }
}

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

Đây là cách viết ngắn gọn nhất:

1. Biến 'u' lưu GCD(a,b).
2. Biến 'x' là số điểm trên biên.
3. Biến 's' là diện tích nhân 2 (a*b).
4. Biến 'y' là công thức Pick biến đổi.

Lưu ý: abs(a*b) là thừa vì a,b đều dương, nhưng giúp đảm bảo tính đúng nếu có số âm.

Công thức Inside có thể được viết lại thành: I = (ab - (a+b+g) + 2)/2 = (ab - a - b - g + 2)/2

Đây là cách hiệu quả nhất về mặt code length và vẫn đảm bảo hiệu năng.

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

Bài học kinh nghiệm

• Định lý Pick (Pick's Theorem) là chìa khóa: Area = I + B/2 - 1, từ đó suy ra công thức tính số điểm bên trong I = (Area*2 - B + 2)/2
• Số điểm trên biên tam giác OAB bằng a + b + gcd(a,b), có thể chứng minh bằng cách đếm điểm nguyên trên từng cạnh và loại bỏ điểm đếm trùng
• Bài toán có thể giải quyết trong O(log(min(a,b))) thời gian nhờ thuật toán Euclid tính GCD nhanh

Lỗi thường gặp

• Quên trừ điểm đếm trùng (O, A, B) khi tính số điểm trên biên, dẫn đến kết quả sai
• Sử dụng số nguyên 32-bit (int) thay vì 64-bit (long long) gây tràn số khi a,b lên tới 10^9, vì a*b có thể lên tới 10^18
• Tính sai công thức Pick: sai thứ tự phép tính hoặc thiếu dấu +2 trong công thức Inside