Hiểu bài toán

Bài toán yêu cầu tìm số nguyên dương $k$ lớn nhất sao cho tổng của $k$ số tự nhiên đầu tiên (tức là $1 + 2 + \dots + k$) không vượt quá $n$. Nói cách khác, cần tìm $k$ lớn nhất thỏa mãn công thức tính tổng các số tự nhiên từ 1 đến k: $\frac{k(k+1)}{2} \le n$. Dữ liệu đầu vào là một số nguyên $n$ (có thể rất lớn, lên tới $10^{18}$).

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

Cách Công thức giải phương trình

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

int main() {
    long long n;
    cin >> n;
    long double t = sqrt((long double)1 + 8.0L*n);
    long long k = (long long)((t - 1) / 2);
    cout << k;
    return 0;
}

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

Phương pháp này dựa trên việc giải phương trình bậc 2 $\frac{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 = \frac{-1 + \sqrt{1 + 8n}}{2}$. Vì $k$ phải là số nguyên dương nên ta chỉ cần lấy phần nguyên của kết quả này. Sử dụng số thực long double để đảm bảo độ chính xác khi tính căn bậc hai cho số $n$ lớn, sau đó ép kiểu về long long.

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin >> n;
    long long l = 1, r = 2000000000; // 2e9 là giới hạn trên an toàn cho k
    long long ans = 0;
    while (l <= r) {
        long long mid = (l + r) / 2;
        long long t = mid * (mid + 1) / 2;
        if (t <= n) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans;
}

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

Phương pháp này sử dụng kỹ thuật tìm kiếm nhị phân để tìm giá trị $k$ thỏa mãn điều kiện. Biến l và r biểu thị cho khoảng giá trị tìm kiếm của $k$. Ở mỗi bước, ta chọn giá trị giữa khoảng (mid) và kiểm tra xem tổng $\frac{mid(mid+1)}{2}$ có nhỏ hơn hoặc bằng $n$ hay không. Nếu có, ta thử tìm giá trị lớn hơn (di chuyển l sang mid + 1), ngược lại thử giá trị nhỏ hơn (r = mid - 1). Phương pháp này đảm bảo tìm ra giá trị chính xác và an toàn về số.

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

Bài học kinh nghiệm

• Bài toán quy về giải phương trình $k(k+1)/2 \le n$.
• Với $n$ lớn, các phép toán số cần được xử lý cẩn thận để tránh tràn số.

Lỗi thường gặp

• Tràn số (Overflow) khi tính tích $k(k+1)$ với $k$ lớn.
• Sai số làm tròn khi tính toán bằng số thực (Floating point error).