Hiểu bài toán

Cho một số nguyên dương N, tìm số nguyên dương lớn nhất x sao cho tổng 1 + 2 + 3 + ... + x không vượt quá N. N có giá trị lên tới 10^9.

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

Cách Vòng lặp cơ bản (Brute Force)

#include <stdio.h>

int main() {
    int N;
    scanf("%d", &N);
    int a = 0, b = 0;
    while (b <= N) {
        a++;
        b += a;
    }
    printf("%d", a - 1);
    return 0;
}

• Time Complexity: O(\sqrt{N})
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất. Ta sử dụng hai biến a (đại diện cho số hạng hiện tại) và b (đại diện cho tổng hiện tại). Trong mỗi bước lặp, ta tăng a lên 1 và cộng dồn vào b. Vòng lặp dừng lại khi tổng b vượt quá N. Giá trị a tại thời điểm đó lớn hơn x thực tế, nên ta trả về a - 1. Do tổng 1+2+...+x xấp xỉ x^2/2, số bước lặp sẽ xấp xỉ sqrt(2*N), rất nhanh đối với N=10^9 (khoảng 45,000 lần lặp).

Cách Phương pháp Toán học (Công thức nghiệm xích

#include <stdio.h>
#include <math.h>

int main() {
    long long n;
    scanf("%lld", &n);

    // Giai phuong trinh x*(x+1)/2 <= n
    // x^2 + x - 2n <= 0
    // Delta = 1 + 8n
    // x = (-1 + sqrt(1 + 8n)) / 2

    double delta = 1 + 8.0 * n;
    long long x = (long long)((sqrt(delta) - 1) / 2);

    printf("%lld", x);
    return 0;
}

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

Tổng 1 + 2 + ... + x bằng x*(x+1)/2. Yêu cầu bài toán là tìm x lớn nhất sao cho x*(x+1)/2 <= N. Đây là một bất phương trình bậc 2: x^2 + x - 2N <= 0. Ta có thể giải phương trình x^2 + x - 2N = 0 để tìm nghiệm biên. Nghiệm dương của phương trình này là x = (-1 + sqrt(1 + 8N)) / 2. Giá trị x nguyên dương lớn nhất thỏa mãn là phần nguyên của biểu thức này. Phương pháp này chạy ngay lập tức (hằng số thời gian).

Cách Tìm kiếm nhị phân (Binary Search)

#include <stdio.h>

int main() {
    long long N;
    scanf("%lld", &N);

    long long left = 1, right = 2000000000; // Nguon goc: sqrt(2*10^9) ~ 44721, chon du phong
    long long ans = 0;

    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (mid * (mid + 1) / 2 <= N) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    printf("%lld", ans);
    return 0;
}

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

Ta có thể coi hàm f(x) = x*(x+1)/2 là một hàm đơn điệu tăng. Ta cần tìm giá trị x lớn nhất sao cho f(x) <= N. Sử dụng tìm kiếm nhị phân, ta sẽ tìm trong khoảng từ 1 đến một giá trị đủ lớn (ví dụ 2*10^9). Nếu f(mid) <= N, thì mid có thể là câu trả lời và ta thử tìm giá trị lớn hơn. Ngược lại, ta phải giảm giá trị xuống. Độ phức tạp là O(log N), rất nhanh.

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

Bài học kinh nghiệm

• Bài toán có thể được quy về giải một bất phương trình bậc 2 hoặc tìm giá trị biên của hàm đơn điệu.
• Với N lên tới 10^9, các thuật toán O(sqrt(N)) hoặc O(log N) đều chấp nhận được.
• Cần chú ý sử dụng kiểu dữ liệu long long để tránh tràn số khi tính toán giá trị tổng hoặc bình phương.

Lỗi thường gặp

• Sử dụng biến kiểu int cho N hoặc biến tích lũy khi N lớn (gây tràn số).
• Lỗi logic trong vòng lặp: tính sai điều kiện dừng hoặc trả về sai giá trị sau khi vòng lặp kết thúc.