DSCP - Đếm số chính phương
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
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~ mà ~L ≤ n ≤ R~). Em hãy giúp Tí lập một chương trình giải quyết việc đó nhé.
Input
- 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.
Giới hạn:
- ~40\%~ số test có ~1 ≤ L ≤ R ≤ 10^4~
- ~40\%~ số test có ~1 ≤ L ≤ R ≤ 10^8, R – L ≤ 10^5~
- ~20\%~ số test có ~1 ≤ L ≤ R ≤ 10^{12}, R – L ≥ 10^9~.
Output
- Một dòng duy nhất ghi số số chính phương nằm giữa ~L~ và ~R~
Sample
Input #1
2 5
Output #1
1
Input #2
3 25
Output #2
4
Hint
- Trong ví dụ ~1~, có duy nhất một số chính phương nằm giữa ~2~ và ~5~ là số ~4~
- Trong ví dụ ~2~, có bốn số chính phương nằm giữa ~3~ và ~25~ là số ~4~, ~9~, ~16~, ~25~
Problem source: Chuyên Sơn La Online Judge
Bình luận
như này
a=sqrt(L) & b=sqrt(r) chạy i từ a-1 đến b kt a <= i*i <=b
bài này các bạn có thể làm bằng cách lấy sqrt(r) - sqrt(l) + (sqrt(l) * sqrt(l) == l)
bạn làm như này thì sẽ bị quá thời gian vì trong 1s máy tính không thể xử lí quá 10^8 phép tính mà đề bài cho 10^9 nên bị tle
khi duyệt từ sqrt(l) -> sqrt(r) mn cần chú ý case sau: 10->100 nếu lấy sqrt --> 3->10 mà 3^2 = 9 thì không nằm trong khoảng 10->100 Vậy thì left sau khi khai căn cần lấy cận trên để nó ko bị làm tròn xuống.
bài này mấy bạn chỉ cần duyệt từ cận trên của n=sqrt(l) đến m=sqrt(r) sau đó lấy m-n+1 là đc