浅析 NC14733 完全平方数 （数学 或 二分）

题目链接：

https://ac.nowcoder.com/acm/problem/14733

题目描述：

多次查询 $[l,r][l,\; r]$ 范围内的完全平方数个数 定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x

输入描述:
第一行一个数n表示查询次数
之后n行每行两个数l,r

输出描述:
对于每个查询，输出一个数表示答案

input:
5
1 3
1 4
2 4
4 4
1 1000000000

output:
1
2
1
1
31622

数据范围:
n <= 100000
0 <= l <= r <= 1000000000

分析+代码：

完全平方数的定义：

完全平方指用一个整数乘以自己例如 $1\ast 11*1$，$2\ast 22*2$，$3\ast 33*3$ 等，依此类推。若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。完全平方数是非负数，而一个完全平方数的项有两个。注意不要与完全平方式所混淆。

思路1（没看数据范围）：

首先想到开一个大数组，用前缀和标记从前i位数中是完全平方数的整数个数。 然而数据范围是：0 <= l <= r <= 1000000000（1e9），空间限制 C/C++ 131072K，最大只能开大约 $3\ast 10^{7}3*10^7$ 的 int 数组，遂放弃。

思路2——数学：

本题相当于给定一个函数 $y=x^{2}y\; =\; x^2$ ，要求求出 $y\in [l,r]y\; \backslash in\; [l,\; r]$ 范围所对应的 $xx$ 的范围内取整数值的个数，这是个连续函数，可以直接首尾相减即可。注意上下界！！！

#include<iostream>
#include<math.h>
using namespace std;
int main () {
	int n;
	cin >> n;
	
	int l, r;
    
	while (n--) {
		cin >> l >> r;
		
		cout << floor(sqrt((double)r)) - ceil(sqrt((double)l)) + 1 << endl;
	}
	
	return 0;
}

思路3——二分（思路2的反向操作）：

虽然前缀和不能开那么大的数组，但是融合前两个思路，可以利用这个函数的一一映射关系，通过二分快速找到上下界即可。注意二分查找函数只适用于在规定范围内有序的序列，注意规定范围。

#include<iostream>
#include<algorithm>
using namespace std;

#define ll long long

const int maxn = 1e5+7;

int a[maxn] = {};

int main () {
	int cnt = 0;
	
	while (cnt*cnt <= 1e9) {
		a[cnt] = cnt*cnt;
		cnt++;
	}
	
	int n;
	cin >> n;
	
	int l, r;	
	while (n--) {
		cin >> l >> r;
		cout << upper_bound(a, a+cnt, r) - lower_bound(a, a+cnt, l) << endl;
	}
	
	return 0;
}