完全平方数(模拟 思维)
完全平方数
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
思路
好像可以不用二分吧……一开始的做法就是直接模拟从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;
} 牛客算法竞赛入门课第三节习题题解 文章被收录于专栏
入门课第三节习题题解
查看13道真题和解析
