2489 小b和灯泡

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

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

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

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

收起

 

输入

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

输出

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

输入样例

3

输出样例

1
打表发现规律:第i^2的灯是亮的,扫描一遍符合的i;复杂度logn
#include<Iostream>
using namespace std;
bool a[];
int main(){
int n;
cin>>n;
int sum=;
for(int i=;;i++){
if(i*i>n)
break;
sum++;
}
cout<<sum<<endl;
return ;
}
 
05-11 20:15