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

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

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

输入:
对于60%的数据:n≤2×106
对于100%的数据:n≤1018

可以看出,星星的亮暗可以看出他变化次数为奇数次还是偶数次,或者说他的整数因子的个数为偶数还是奇数。
比如星星刚开始为暗的,变化偶数次亮暗不变,变化奇数次亮暗发生转变。
再比如编号为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;
ll sum = 1;
map<long long, int> a;
void aaa() {
    a[1] = 1;
    for (ll i = 2; i * i <= n; i++) {
        sum++;
    }
}
int main() {
    scanf("%lld", &n);
    aaa();
    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)));
}

sqrt(n)为求n以内完全平方数的个数