题目

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

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

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

解析

1）知识点

  • 这道题不难，完全就是一道简单的数学题。但是按题目上面说的搞二分，也完全可以。

2）看题目

  • 这道题目就是叫我们查询一个区间内的平方数个数。

3）算法分析

  1. 因为数据范围大小有1e9的大小，所以不可能开个数组用前缀和什么的。
  2. 首先我们讲一下数学思路：
    1. 因为平方数开了根号之后就是一段连续的数。所以我们对范围开个根号，取中间的整数区间，求出长度就好了：就是sqrt(r)-sqrt(l)+1。
  3. 然后就是二分了：
    1. 我们可以先把所有的平方数存起来，然后对左右区间进行二分查找。
    2. 二分很方便，我们只要用lower_bound和upper_bound就可以了：就是upper_bound(a,a+n,r) - lower_bound(a,a+n,l)。
  4. 就这样，很简单的。

4）算法操作

  1. 操作？没啥操作，就是输入输出。
  2. 数学：sqrt(r)-sqrt(l)+1。
  3. 二分：upper_bound(a,a+n,r) - lower_bound(a,a+n,l)。

5）打代码

  1. 输入。
  2. 输出。
  3. 看我代码~

AC代码（数学） 

#include <iostream>
#include <cmath>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

int main() {
    IOS;
    int T; cin >> T;
    while (T--) {
        int l, r; cin >> l >> r;
        cout << floor(sqrt(1.0 * r)) - ceil(sqrt(1.0 * l)) + 1 << endl;
    }
    return 0;
}
//函数区

AC代码（二分） 

#include <iostream>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e6 + 7;
int info[MAX];
//全局变量区

int main() {
    IOS;
    int len = 0;
    for (int i = 0; i * i <= 1e9; i++)
        info[len++] = i * i;
    //平方数数组初始化
    int T; cin >> T;
    while (T--) {
        int l, r; cin >> l >> r;
        cout << upper_bound(info, info + len, r) - lower_bound(info, info + len, l) << endl;
    }
    return 0;
}
//函数区