链接:https://ac.nowcoder.com/acm/problem/14733
来源:牛客网
题目描述
多次查询[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
题目解析:极其关键的一点是:注意到这个题的范围10的九次方,我们可以省着点数组开到31000多就好了。
首先按看到题目,我的思路是暴力枚举,但是显然复杂度过高了,n^2级别的复杂度肯定过不了,然后我就想把该区间上的每个数去找前面的数,不过这次是用二分法,然而还是不过,我又想到可不可以把10^9之前的完全平方数全部求出来存到一个数组中去,再看每个区间有多少个这里面的数,基于此,我首先将该区间段的每一个数都去二分,二分那个已经存好的数组,没过、复杂度还是太高;然后我就针对每个区间段,缩小数组长度,把数组的下标拿出来,a[左]<=区间的最小数,a[右]大于等于区间的最大数,不过这次我用FOR循环遍历前面的数,没过;最后我将区间端点拿出来,在完全平方数组里二分,找到端点,再返回,这样把查询区间段缩短,好歹给我过了。。。
总之,这就是一个寻找最优解的过程。
#include<iostream> #include<string> #include<string.h> #include <algorithm> #include <cstdio> using namespace std; int a[100000]; int panduan(int s) { if(s==0)return 1; else { int w,l,r; l=0; r=31650; w=(l+r)/2; while(1) { //cout<<w<<endl; if(a[w]==s) { return w; } if(a[w]<s) { l=w; w=(l+r)/2; } if(a[w]>s) { r=w; w=(l+r)/2; }if(w==l)return w; } } } int diaoyong(int c,int d) { int j,sum,m,n; sum=0;m=0;n=0; if(c==0)sum=1; m=panduan(c); n=panduan(d); for(j=m;j<=n;j++) { if(a[j]>=c&&a[j]<=d) { sum++; } } return sum; } int main() { int z; for(z=1;z<=31650;z++) { a[z]=z*z; } int w,j,t,a,b; cin>>t; for(j=0;j<t;j++) { cin>>a>>b; w=diaoyong(a,b); cout<<w<<endl; } system("pause"); return 0; }