牛客OI赛制测试赛2D星光晚餐题解

牛客OI赛制测试赛2D星光晚餐题解

题目

Johnson和Nancy要在星光下吃晚餐。这是一件很浪漫的事情。为了增加星光晚餐那浪漫的氛围，他拿出了一个神奇的魔法棒，并且可以按照一定的规则，改变天上星星的亮暗。
Johnson想考考Nancy，在他挥动魔法棒后，会有多少颗星星依旧闪耀在天空。他知道，Nancy一定会一口说出答案。Nancy当然知道怎么做啦，但她想考考你！
Johnson先将天上n个星星排成一排，起初它们都是暗的。他告诉他的妹子，他将挥动n次魔法棒，第i次挥动会将编号为i的正整数倍的星星的亮暗反转，即亮的星星转暗，暗的星星转亮。Johnson想问Nancy，最终会有多少个星星依旧闪亮在天空。
输入描述:
一个整数n，含义请见题目描述。
输出描述:
一个整数ans，即n次操作后会有多少个星星依旧闪亮。
示例1
输入
3
输出
1

示例2
输入
7
输出
2

分析

一道结论题，和洛谷中的一道关路灯很像，我们可以分析，知道因数个数是奇数的可能会亮，而这样的数只可能是完全平方数，所以输出sqrt（n）即可。
上程序

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long n;
int main(){scanf("%lld",&n);n=sqrt(n);printf("%lldn",n);return 0;
}