题目描述

多次查询[l,r]范围内的完全平方数个数

定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x

输入描述: 

第一行一个数n表示查询次数
之后n行每行两个数l,r

输出描述: 

对于每个查询，输出一个数表示答案
示例1

输入 

5
1 3
1 4
2 4
4 4
1 1000000000

输出 

1
2
1
1
31622

备注: 

n <= 100000
0<= l <= r <= 1000000000

思路

好像可以不用二分吧……一开始的做法就是直接模拟从sqrt(l)到sqrt(r)走一遍循环累加，复杂度O(nlogr)。后来发现，中间都是连续的啊，所有个数用两个端点一减就行了，注意号边界情况就行，sqrt(l)需要向上取整，复杂度O(n)。

代码1(模拟 O(nlogr)) 

//完全平方数(模拟) 
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n , l , r;
	scanf("%d" , &n);
	while(n--)
	{
		scanf("%d %d" , &l , &r);
			
		int m = sqrt(l) , ans = 0;
		if(m * m != l)
			m++;
		for(int i = m ; i * i <= r ; i++)
			ans++;
		
		printf("%d\n" , ans);
	}
	return 0;
}

代码2(思维 O(n)) 

//完全平方数(思维)
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
 	int n , l , r;
 	scanf("%d" , &n);
 	
 	while(n--)
 	{
		scanf("%d %d" , &l , &r);	 
	 	int m = sqrt(l);
	 	if(m * m == l)
	 		m--;
	 	printf("%d\n" , (int)sqrt(r) - m + 1);
	}
	return 0; 
}