Hiểu bài toán

Cho một số nguyên dương K. Đếm số lượng các cặp số nguyên dương (x, y) sao cho x + y = K và x < y. Ví dụ: K = 5 thì các cặp (1, 4), (2, 3) thỏa mãn, đáp án là 2.

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

Cách Mô phỏng vòng lặp (Brute Force)

ll dem = 0;
for(ll i = 1; i <= n / 2; i++) {
    ll j = n - i;
    dem++;
    dem += j - i - 1;
}

• Time Complexity: O(K)
• Space Complexity: O(1)

Duyệt tất cả giá trị x từ 1 đến K/2. Với mỗi x, tính y = K - x. Nếu x < y thì tăng biến đếm. Trong code tối ưu hóa, ta nhận thấy số lượng y > x là (y - x - 1), cộng thêm 1 (cho cặp (x, y) chính xác).

Cách Công thức toán học

long long n = (K - 1) / 2;
long long kq = n * (K - 1 - n);

• Time Complexity: O(1)
• Space Complexity: O(1)

Tổng của các cặp số nguyên dương dương bằng K-1 (vì x, y >= 1). Gọi n là số nguyên lớn nhất sao cho n < K/2 (tức n = floor((K-1)/2)). Số lượng cách chọn 2 số phân biệt có tổng là K-1 là tổ hợp chập 2 của K-1, nhưng ta cần x < y. Số lượng cặp (x, y) dương thỏa mãn x + y = K với x < y chính là số cách chọn số thứ nhất x từ 1 đến n (tổng cộng n cách), và với mỗi x thì y được xác định duy nhất và luôn > x. Do đó đáp án là n.

Cách Công thức tối ưu

long long A = (K - 1) / 2;
long long ans = A * (K - A - 1);

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là biến thể của công thức toán học. A = floor((K-1)/2) là số lượng số nguyên dương nhỏ hơn K/2. Tuy nhiên, phép nhân A * (K - A - 1) trong code có vẻ là một cách tính tổng số lượng các cặp (x, y) thỏa mãn điều kiện tổng là K (có thể bao gồm cả x = y hoặc thứ tự ngược lại). Thực tế, với điều kiện x < y, đáp án đơn giản chỉ là floor((K-1)/2).

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

Bài học kinh nghiệm

• Bài toán quy về tìm số cách chọn hai số nguyên dương phân biệt có tổng bằng K, với thứ tự (x, y) được xác định.
• Số lượng cặp số nguyên dương dương có tổng bằng K là số các số nguyên dương nhỏ hơn K/2.

Lỗi thường gặp

• Quên kiểm tra điều kiện x < y dẫn đến đếm dư.
• Sử dụng biến số nguyên nhỏ (int) gây tràn số khi K lớn (nên dùng long long).
• Xử lý sai trường hợp K chẵn (ví dụ K=4, cặp (2,2) không thỏa mãn x<y).</li>