此题取自牛客网 链接为:星光晚餐

Johnson 和 Nancy 要在星光下吃晚餐。这是一件很浪漫的事情。为了增加星光晚餐那浪漫的氛围,他拿出了一个神奇的魔法棒,并且可以按照一定的规则,改变天上星星的亮暗。 Johnson 想考考 Nancy ,在他挥动魔法棒后,会有多少颗星星依旧闪耀在天空。他知道,Nancy 一定会一口说出答案。

Nancy 当然知道怎么做啦,但她想考考你!
Johnson 先将天上 n 个星星排成一排,起初它们都是暗的。
他告诉他的妹子,他将挥动 n 次魔法棒,第 i 次挥动会将编号为 i 的正整数倍的星星的亮暗反转,即亮的星星转暗,暗的星星转亮。Johnson 想问 Nancy ,最终会有多少个星星依旧闪亮在天空。

输入:
对于 60% 的数据:n ≤ 2 × 1000000
对于 100% 的数据:n ≤ 1000000000000000000

可以看出,星星的亮暗可以看出他变化次数为奇数次还是偶数次,或者说他的整数因子的个数为偶数还是奇数。
比如星星刚开始为暗的,变化偶数次亮暗不变,变化奇数次亮暗发生转变。
再比如编号为 10 的这个星星,第一次,第二次,第五次,第十次。共变化四次,四为偶数。亮暗不变。
再再比如编号为 9 的星星,第一次,第三次,第九次,共三次发生变化,三为奇数。所以最终他从暗变为亮的。
所以得出结论,最终会亮的星星他们编号有个共同特征就是他们为完全平方数!因为只有完全平方数整数因子为奇数个,才会被变化奇数次! 100 课星星,哪些会亮呢?答案为:1 ,4 ,9 ,16 ,25 ,36 ,49 ,64 ,81 ,100

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,sum = 1;
int main() {
    scanf("%lld", &n);
    for (ll i = 2; i * i <= n; i++)
        sum++;
    printf("%lld\n", sum);
    return 0;
}

直接开方也可以代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
int main()
{
    scanf("%lld",&n);
    printf("%lld",(ll)floor(sqrt(n)));
}