题目链接: http://class.51nod.com/Challenge/Problem.html#problemId=2489
一, 题目描述
小 b 有 n 个关闭的灯泡, 编号为 1...n.
小 b 会进行 n 轮操作, 第 i 轮她会将编号为 i 的倍数的灯泡的开关状态取反, 即开变成关, 关变成开.
求 n 轮操作后, 有多少灯泡是亮着的.
输入:
输入一个数字表示灯泡数 n, 其中 1<n≤10000000
输出:
输出一个数字表示最终亮着的灯泡数
样例输入:
3
样例输出:
1
二, 思路描述
用暴力的方法肯定会超时的, 所以肯定不可以
对于第 1 个灯泡, 第 1 次操作会反转开关. 最终状态是开
对于第 2 个灯泡, 第 1,2 次操作会反转开关. 最终状态是关
对于第 3 个灯泡, 第 1,3 次操作会反转开关. 最终状态是关
对于第 4 个灯泡, 第 1,2,4? 次操作会反转开关. 最终状态是开
对于第 i 个灯泡, 第 i 的因子次操作都会使开关反转.
所以因子个数为偶数的最终状态是关, 因子个数为奇数的最终状态是开. 只有完全平方数的因子数是奇数.
因为如果 A 是 C 的因数, 则 C/A 也是 C 的因数. 因此因数总是成对出现的, 只有当 C/A=A 时, C 的因数个数才可能是奇数.
所以只需要统计出 1-n 中有多少个完全平方数即可.
三, 代码
- #include
- #include
- using namespace std;
- int main(){
- int n, ans=0;
- cin>> n;
- for(int i = 1;i*i <= n;i++){
- ans++;
- }
- cout << ans << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3530095.html