首页 > 试题广场 >

完全平方数

[编程题]完全平方数
  • 热度指数：30 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解

多次查询[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
算法知识视频讲解
开通博客
头像 Soulless7s
发表于 2020-05-21 22:18:48
题意很简单，求[l,r]范围内的完全平方数个数，0<= l <= r <= 1000000000；因为sqrt(1000000000)=31622，所以我们可以写一个0-31622的递增数组，在这个数组里二分找答案找一个左边界L使得L²>=l，再找一个右边界使得R²>r 展开全文
去ta的博客 赞 (22) 回复(0) 收起
头像 东溪看水
发表于 2020-06-04 16:19:57
解题思路 多次查询 范围内的完全平方数个数。定义整数 为完全平方数当且仅当可以找到整数 使得 。 令 ，。 范围内的完全平方数为 ，共有 个数；如果 ，则所求范围内还包括完全平方数 ，共有 个数。 C++代码 #include<iostream> #include<cm 展开全文
去ta的博客 赞 (15) 回复(0) 收起
头像 19_hanhan
发表于 2020-06-07 00:43:41
题目 题目描述： 多次查询[l,r]范围内的完全平方数个数。 定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x 输入描述： 第一行一个数n表示查询次数 之后n行每行两个数l,r 输出描述： 对于每个查询，输出一个数表示答案 解析 1）知识点 展开全文
去ta的博客 赞 (8) 回复(1) 收起
头像 ziuch
发表于 2020-08-24 15:18:48
题目描述 多次查询[l,r]范围内的完全平方数个数 定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x 输入描述: 第一行一个数n表示查询次数 之后n行每行两个数l,r 输出描述: 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 usx21145328
发表于 2022-01-14 11:35:27
二分条件要想清楚，题目是找到l到r里的平方数的个数，其实就是在l到r里找0、1、2、3、4.....到31622这些数的平方，可以找左边界假设是x1，要找到满足x1 * x1>=l的第一个数，然后找右边界假设是x2，要找到满足x2 * x2<=r的最后一个数，那么x1到x2之间的数就是l 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-05-30 12:43:11
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K 64bit IO Format: %lld 题目描述 多次查询[l,r]范围内的完全平方数个数 定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x 输入描述: 第 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Typecoh
发表于 2021-01-27 21:07:59
#include<stdio.h> #include<math.h> int main() { long long int l, r; int n; int cnt = 0; scanf("%d", &n); for (int 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 青春不悔
发表于 2020-05-29 14:20:55
链接：https://ac.nowcoder.com/acm/problem/14733来源：牛客网 题目描述多次查询[l,r]范围内的完全平方数个数 定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x 输入描述:第一行一个数n表示查询次数之后n行每行两个数l,r输出描述:对于每个查询，输出 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 MoXq
发表于 2022-07-23 10:19:48
完全平方数 *题目描述 * 多次查询[l,r]范围内的完全平方数个数 定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x 输入描述: 第一行一个数n表示查询次数 之后n行每行两个数l,r 输出描述: 对于每个查询，输出一个数表示答案 思路： 用一个数组存下标为i的完全平方数，再用upper_ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 回归梦想
发表于 2020-04-17 14:29:55
@[TOC]传送 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K64bit IO Format:%lld 题目描述 多次查询[l,r]范围内的完全平方数个数 定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x 输入描述: 第一 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

二分 预处理
上传者：牛客301599号
难度：
0条回答 114浏览

热门推荐

通过挑战的用户

查看代码

相关试题

完全平方数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号