#359. CSL20171 - Đếm số chính phương

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Hôm nay Tí được học về số chính phương, đó là những số là bình phương của một số tự nhiên (chẳng hạn 0, 1, 4, 9, 16… ). Tí rất thích số chính phương và Tí muốn đếm xem giữa hai số nguyên dương L, R bất kỳ có bao nhiêu số chính phương (tức là những số chính phương n L ≤ n ≤ R ). Em hãy giúp Tí lập một chương trình giải quyết việc đó nhé.

Dữ liệu vào:

  • Một dòng duy nhất chứa hai số nguyên dương L, R cách nhau bởi một dấu cách.

Dữ liệu ra:

  • Một dòng duy nhất ghi số số chính phương nằm giữa L R

Ví dụ:

Dữ liệu vào:
2 5
Dữ liệu ra:
1
Dữ liệu vào:
3 25
Dữ liệu ra:
4
Giải thích:
  • Trong ví dụ 1 , có duy nhất một số chính phương nằm giữa 2 5 là số 4
  • Trong ví dụ 2 , có bốn số chính phương nằm giữa 3 25 là số 4 , 9 , 16 , 25

Giới hạn:

  • 40\% số test tương ứng với 40\% số điểm của bài toán có 1 ≤ L ≤ R ≤ 10^4
  • 40\% số test khác tương ứng với 40\% số điểm của bài toán có 1 ≤ L ≤ R ≤ 10^8, R – L ≤ 10^5
  • 20\% số test còn lại tương ứng với 20\% số điểm của bài toán có 1 ≤ L ≤ R ≤ 10^{12}, R – L ≥ 10^9 .