(npcp.*)

Mọi dữ liệu trong máy tính đều được số hòa, tức là có dạng dãy các bit 0 và 1. Mọi thao tác xử lý dỡ liệu trên máy tính cuối cùng đều dẫn đến xử lý các bit. Vì vậy khi thực hiện xong tính toán, máy tính phải giải mã kết quả từ hệ nhị phân sang hệ thập phân để con người có thể hiểu và kiểm tra được. Việc đổi số nhị phân có dạng \(d_{k}d_{k - 1}\ldots d_{1}d_{0}\) sng số thập phân thực chất chỉ là việc tính giá trị biểu thức \(d_{k} \times 2^{k} + d_{k - 1} \times s^{k - 1} + \ldots + d_{1} \times 2^{1} + d_{0} \times 2^{0}\).

Ví dụ dãy bit 111 trong hệ nhị phân chuyển sang hệ thập phân sẽ là số 7; vì \(111_{2} \rightarrow 1 \times 2^{2} + 1 \times 2^{1} + 1 \times 2^{0} = 7_{10}\)

Hôm nay bạn hãy viết chương trình giải bài toán như sau: Cho dãy bit của hai số nguyên dương \(a,\ b\ (1 \leq a < b < 10^{18})\) trong hệ nhị phân.

Yêu cầu: đếm số lượng số chính phương có trong đoạn từ \(a\) đến \(b\), Biết rằng một số nguyên dương được gọi là số chính phương nếu căn bậc hai của nó là một số nguyên dương.

Dữ liệu vào:

+ Dòng thứ nhất là dãy bit của số nguyên dương \(a\) trong hệ nhị phân;

+ Dòng thứ hai là dãy bit của số nguyên dương \(b\) trong hệ nhị phân;

Kết quả:

+ Ghi một số nguyên là kết quả bài toán

Ví dụ:

Giải thích:

• Số 111 trong hệ nhị phân là số 7 trong hệ thập phân

• Số 10011 trong hệ nhị phân là số 19 trong hệ thập phân

Như vậy trong đoạn 7 đến 19 có hai số chính phương là 9 và 16

Ràng buộc dữ liệu:

• 75% số test ứng với \(1 < a < b \leq 10^{9}\)

• 25% test ứng với \(10^{9} < a < b < 10^{18}\)