2489 小b和灯泡

1. 2 秒
 
2. 262,144 KB
 
3. 10 分
 
4. 2 级题

 

小b有n个关闭的灯泡，编号为1...n。

小b会进行n轮操作，第i轮她会将编号为i的倍数的灯泡的开关状态取反，即开变成关，关变成开。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

求n轮操作后，有多少灯泡是亮着的。

 收起  

输入

输入一个数字表示灯泡数n，其中1＜n≤10000000

输出

输出一个数字表示最终亮着的灯泡数

输入样例

3

输出样例

1
打表发现规律：第i^2的灯是亮的，扫描一遍符合的i；复杂度logn

#include<Iostream>
using namespace std;
bool a[1000];
int main(){
    int n;
cin>>n;
int sum=0;
for(int i=1;;i++){
    if(i*i>n)
    break;
    sum++;
}
cout<<sum<<endl;
    return 0;
} 

 

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄