变换的灯

有N个灯放在一排（编号从1到m)，如果对灯执行n此i操作(i = 1,2,3....n),对于一次i操作的定义如下，将一次i操作定义为，（将编号为i的倍数的灯进行翻转，开到关，关倒开），那么如果开始所有灯都是关闭的，那么进行n次操，之后，会有多少个灯是打开的。

我的思路：

解法一：模拟.

#define max_n 10000001
int vis[max_n]; 
int solve_first(int n){
	int i,j,count=0;
	memset(vis,0,sizeof(vis));
	for(i=1;i<=n;i++){
		for(j=1;i*j<=n;j++){
			vis[i*j]=!vis[i*j];
		}
	}
	for(i=1;i<=n;i++){
		count +=vis[i];
	}
	return count;
}

解法二：

(1)被操作奇数次的灯状态发生改变，偶数次数状态不变，因此只需求编号为i的灯的操作次数的奇偶性。

不难证明i

当i是完全平方数时其因数个数实奇数，否则是偶数。

证明：

假设i是完全平方数，有x=sqrt(i);

对于i有约数 1<=a1,a2.. x i/a1,i/a2...i是奇数个其他约数是对称的，x是只有一个，因此约数个数为奇数。

假设i不是完全平方数，所有i的约数a都有i/a与之对应，因此一定是偶数。

（2）由（1） 问题变为求n之内的完全平方数个数。不难得出所求就是sqrt(n)向下取整。

int solve_two(int n){
	return (int)pow(n*1.0,0.5);
}