4.11 每日一题题解

完全平方数

• 题目链接：https://ac.nowcoder.com/acm/contest/37/A

涉及知识点：

• 暴力/二分

solution：

• (祝大家周末愉快)
• ([1，n]区间的完全平方数的个数等于) (sqrt{n})
• ([L，R]区间的完全平方数的个数可以理解为) $sqrt{R} - sqrt{L-1} $
• (0也是完全平方数，L和R是否为0判断一下即可)
• (当然将所有平方数放入数组，lowerbound二分也是时间复杂度允许的可行解)

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int t,l,r;
    cin>>t;
    while(t--){
        cin>>l>>r;
        if(l != 0)
            l = sqrt(l-1) + 1;
        if(r != 0)
            r = sqrt(r) + 1;
        else
            r = 1;
        cout<<r - l<<endl;
    }
    return 0;
}