Hiểu bài toán

Xác định xem một số nguyên dương N có phải là số tam giác hay không. Số tam giác là số có thể biểu diễn dưới dạng tổng của hai số nguyên liên tiếp (ví dụ: 1 = 1, 3 = 1+2, 6 = 1+2+3, 10 = 1+2+3+4, ...). Nói cách khác, ta cần kiểm tra xem是否存在 một số nguyên dương k sao cho k(k+1)/2 = N.

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

Cách Duyệt qua các số tam giác

#include <iostream>
using namespace std;

int main() {
    freopen("triangular.inp", "r", stdin);
    freopen("triangular.out", "w", stdout);
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        long long sum = 0;
        long long k = 1;
        while (sum < n) {
            sum += k;
            if (sum == n) {
                cout << 1 << "\n";
                break;
            }
            k++;
        }
        if (sum != n) cout << 0 << "\n";
    }
    return 0;
}

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

Phương pháp này dựa trên định nghĩa trực tiếp của số tam giác. Ta bắt đầu với k = 1 và tính tổng S = 1 + 2 + ... + k. Nếu S bằng N thì N là số tam giác. Nếu S vượt quá N thì dừng lại. Số lần lặp phụ thuộc vào giá trị của k, mà k xấp xỉ bằng sqrt(2*N). Do đó độ phức tạp là O(sqrt(N)).

Cách Giải phương trình bậc 2

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("triangular.inp", "r", stdin);
    freopen("triangular.out", "w", stdout);
    int T;
    cin >> T;
    while (T--) {
        long long N;
        cin >> N;
        // Kiểm tra xem 8*N + 1 có phải là số chính phương hoàn hảo không
        long long d = 1 + 8LL * N;
        long long s = sqrt(d);
        // Kiểm tra s*s == d và (-1 + s) chia hết cho 2
        if (s * s == d && (-1 + s) % 2 == 0) {
            cout << 1 << "\n";
        } else {
            cout << 0 << "\n";
        }
    }
    return 0;
}

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

Công thức tổng quát của số tam giác là: k(k+1)/2 = N. Biến đổi phương trình ta được k^2 + k - 2N = 0. Áp dụng công thức nghiệm của phương trình bậc 2, ta có k = (-1 + sqrt(1 + 8N))/2. N là số tam giác nếu và chỉ nếu:

1. 1 + 8N là một số chính phương hoàn hảo.
2. Căn bậc hai của nó, sqrt(1 + 8N), là một số nguyên.
3. (-1 + sqrt(1 + 8N)) chia hết cho 2 (tức là k là số nguyên). Điều này cho phép kiểm tra trong thời gian hằng số O(1).

Cách Kiểm tra trực tiếp với số học

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("triangular.inp", "r", stdin);
    freopen("triangular.out", "w", stdout);
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        // Tính k xấp xỉ và kiểm tra
        int x = sqrt(2LL * n);
        // Kiểm tra x*(x+1) == 2*n
        if (x * (x + 1) == 2 * n) cout << 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}

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

Đây là biến thể tối ưu của phương pháp giải phương trình bậc 2. Thay vì kiểm tra tính chính phương của 8N+1, ta tính k xấp xỉ bằng cách lấy căn bậc hai của 2N (vì k ≈ sqrt(2N)). Sau đó, ta chỉ cần kiểm tra trực tiếp xem k(k+1) có bằng 2N không. Nếu bằng, N là số tam giác. Cách này tránh được các phép chia lẻ và chỉ sử dụng phép toán nhân và cộng, rất hiệu quả và dễ hiểu.

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

Bài học kinh nghiệm

• Số tam giác có tính chất đặc biệt: N = k(k+1)/2. Biến đổi phương trình này thành phương trình bậc 2 để kiểm tra.
• Một số N là số tam giác khi và chỉ khi 8N + 1 là số chính phương hoàn hảo.
• Kiểm tra trực tiếp k(k+1) == 2N với k = floor(sqrt(2N)) là cách hiệu quả nhất về mặt tính toán.

Lỗi thường gặp

• Làm tròn sai khi tính căn bậc hai (sqrt) cho các số lớn, dẫn đến sai lệch trong kiểm tra. Cần sử dụng hàm sqrt cho số nguyên và kiểm tra kỹ bằng phép nhân.
• Tràn số nguyên khi tính 8*N. Cần ép kiểu sang kiểu dữ liệu lớn hơn (ví dụ: long long) trước khi nhân.
• Sử dụng kiểu dữ liệu float/double cho các phép tính số học có thể gây sai số do độ chính xác giới hạn. Nên ưu tiên sử dụng kiểu số nguyên (integer) và các phép toán chính xác.