完全平方数
完全平方数
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
题解
本题还是比较好想的，直接求的话肯定不划算，预处理一下所有的完全平方数然后查找就可以。
需要注意一点的就是一定别忘了0！！！
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
#define ll long long
ll a[N];
void init(){
for(ll i=0;i<N;++i){
a[i]=i*i;
}
}
int main(){
int n;
scanf("%d",&n);
init();
while(n--){
ll l,r;
scanf("%lld%lld",&l,&r);
l=lower_bound(a,a+N,l)-a;
r=upper_bound(a,a+N,r)-a;
printf("%lld\n",max(r-l,0LL));
}
}
杂题题解 文章被收录于专栏
各种各样题目的题解
安克创新 Anker稳定性 10人发布
投递安克创新 Anker等公司6个岗位 >