[牛客] B-完全平方数

前言

使用stl的二分,最好最好最好最好下标要从0开始啊 t a g : tag : tag:二分 数学 题意 : 思路 : l ≤ x ≤ r l\le x \le r l≤x≤r

l ≤ x ≤ r \sqrt l \le \sqrt x \le \sqrt r l ​≤x ​≤r ​

又因为 l , r ≤ 1 0 9 l,r\le10^9 l,r≤109因此我们可以预处理出 x \sqrt x 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