G2027 [GESP202606 二级] 完全平方数计数 题解

知识点：循环枚举、完全平方数、区间计数。

解题思路

枚举正整数根i直到ii>r，统计满足ii≥l的项。

为什么正确

每个正完全平方数具有唯一正根，按根枚举不遗漏也不重复。

易错点

左右端点均包含；本题按正平方数枚举，根从1开始。

复杂度

时间O(√r)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int l,r,ans=0;
    cin>>l>>r;
    for(int i=1;i*i<=r;i++)ans+=(i*i>=l);
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用6个自行生成的测试点。