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, PyPy, 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
cái này có công thức nha: C++
include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l, r;
int main(){ iosbase::syncwith_stdio(false); cin.tie(0), cout.tie(0);
}
include <bits/stdc++.h>
define ll long long
using namespace std; ll a,b,A,B,S=0; int main() { cin>>a>>b; A=sqrt(a); B=sqrt(b); for(ll i=A-1;i<=B;i++){ if(ii>=a && ii<=b){ S++; } } cout<<S; return 0; }
include <iostream>
include <cmath>
using namespace std;
int main() { // Tối ưu tốc độ nhập xuất iosbase::syncwith_stdio(false); cin.tie(NULL);
}
dành cho bạn nào chưa biết thì cái này gemini làm hộ tôi dùng tốt cực
như này này
con c*c đù má mày tự làm đi thằng ngu si
include <bits/stdc++.h>
using namespace std; long long a,b,A,B,dem=0; int main() { cin>>a>>b; A=sqrt(a); B=sqrt(b); for(long long i=A-1;i<=B;i++) { if(ii>=a && ii<=b) { dem++; } } cout<<dem; return 0; }
sai kia e
Ai làm full AC không cho mình xin code
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