[牛客] B-完全平方数

前言

使用stl的二分,最好最好最好最好下标要从0开始啊
$tag:$二分数学
题意 :

思路 :
$l\le x\le r$

$\sqrt{l}\le \sqrt{x}\le \sqrt{r}$

又因为$l,r\le 10^9$因此我们可以预处理出$\sqrt{x}$数组

最后通过二分确定开方区间,开方区间的大小就是答案

code :

int a[N];
int i;

void init(){
    
	Fup(i,1,1e5)a[i] = i;
}

void solve(){
    
	int l,r;cin>>l>>r;
	int n = 1e5;
	
	int L =  lower_bound(a+1,a+1+n,sqrt(l)) - a;
	int R =  upper_bound(a+1,a+1+n,sqrt(r)) - a;
	cout<<max(R-L,0)<<endl;
}

int main(){
    
	init();
	
	int t;cin>>t;while(t--)
    solve();
    return 0 ;
}