Bài 2: Đếm số chính phương (HSG 9 Hưng Yên 2025-2026)

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Số chính phương là một số nguyên dương có giá trị bằng tích của hai số nguyên bằng nhau. Cho hai số nguyên dương \(L\) và \(R\). Hãy đếm số lượng các số chính phương trong đoạn \([L; R]\).

Yêu cầu: Hãy giúp bạn học sinh giải bài toán nói trên.

Input

Một dòng chứa hai số nguyên dương \(L\) và \(R\) (\(0 < L \leq R \leq 10^{18}\)) phân biệt với nhau bởi một dấu cách.

Output

Một số nguyên duy nhất là kết quả của bài toán.

Scoring

Subtask \(1\) (\(70\%\) số điểm): \(0 < L \leq R \leq 10^6\).
Subtask \(2\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

1 10

Output

Note

Từ \(1\) đến \(10\) có \(3\) số chính phương là \(1; 4; 9\).

Test 2

Input

20 80

Output

Note

Từ \(20\) đến \(80\) có \(4\) số chính phương là \(25; 36; 49; 64\).

Test 3

Input

26 30

Output

Note

Từ \(26\) đến \(30\) không có số chính phương nào.

Bình luận (5)

Tải bình luận...