Cho dãy số \(u_n = n^2 + 1, n \geq 1\) và giá trị \(x\). Hãy tìm phần tử của dãy số nhỏ nhất thỏa mãn lớn hơn hoặc bằng \(x\)

Dữ liệu vào Specification

• Dòng đầu ghi số nguyên dương \(n\) (\(0 < n \le 10^6\)).
• Dòng 2 ghi số nguyên dương \(t\) (\(0 < t \le 10^5\))
• t dòng sau mỗi dòng ghi số nguyên dương \(x\) (\(0< x \le 10^{12}\)).

Dữ liệu ra Specification

• In ra t dòng, dòng thứ \(i\) ghi số kết quả tương ứng là phần tử nhỏ nhất của dãy số lớn hơn hoặc bằng \(x\) tương ứng.

Ví dụ

Giải thích: Dãy đã cho được liệt kê ra như sau: \(2, 5, 10, 17, 26, 37, 50, 65, 82, 101\). Với 5 test \(x = 1, 5, 10, 20, 50\) thì ta có các phần tử thỏa mãn tương ứng là: \(u_1 = 2, u_2 = 5, u_3 = 10, u_5 = 26, u_7 = 50\) là các số nhỏ nhất thuộc dãy thỏa mãn lớn hơn hoặc bằng \(x\)

Để chặt nhị phân phần tử nhỏ nhất lớn hơn \(x\) ta sử dụng hàm sau:

ll  chat1(ll x)
{
    ll dau = 1, cuoi = n;
    while(dau<=cuoi)
    {
        ll giua = (dau + cuoi)/2;
        if(a[giua]>=x) 
        {
            kq = a[giua];
            cuoi = giua - 1;
        }
        else
            dau = giua + 1;
    }
    return kq;
}