通宵教室

Description

高校扩招，教室一度变得很紧张。学生白天上自习的地方较少，晚上教室又闲置着，怎样才能充分利用教学资源，扩大学生自习时空呢？通宵教室解决学生自习空间有限和教学资源不充分利用的问题。开放通宵教室促进了学生学习观念的转变，以前课堂内外基本上是听老师安排，现在是学生自觉在学习。晚上学习效率高、生理调节能力强的学生已经尝到了甜头。好学、考研、辅修、创作的学生又有了一片新的学习时空。
但是通宵教室对传统的学生管理工作带来了一系列的问题。如果通宵教室的利用率不高的话，将教室的所有灯都打开，还会极大地浪费能源。
现在学校对通宵教室灯光使用做一个新的尝试。假设有N个人使用通宵教室，教室里有N盏灯，每个人和每盏灯都有一个编号。开始所有的灯都没打开，第一个人进教室将所有的灯都打开，第二个人将所有的偶数号的灯都关掉，第三个人对所有3的倍数的灯进行如下操作：如果灯开着，就将它关掉，如果灯关着，就将它打开，……，第i个人对所有i的倍数的灯进行如下操作：如果灯开着，就将它关掉，如果灯关着，就将它打开，重复这样的过程，一直到第N个人完成这样的操作。
现在，教室管理员向你求助，他希望知道，完成这样的过程后，教室里开着的灯还有多少盏？

Input

有多组测试数据。第一行是一个正整数T（1<=T<=10000），表示有多少组测试数据。
以下有T行，每行一个测试数据，包含唯一的一个正整数N(1 <= n < 2^32,)。

Output

对于每个测试数据，输出一行包含唯一的一个整数:表示完成这样的过程后，教室里开着的灯的盏数。

Sample Input

2
1
2

Sample Output

1
1

思路一

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 #include <string.h>
 5 #define max 100000000  
 6 using namespace std;
 7 
 8 int main()
 9 {
10     int n,i,j,a[max],count,t;
11     cin>>t;
12     while (t--)
13     {count=0;
14         cin>>n;
15         memset(a,0,sizeof(a));
16         for (i=1;i<=n;i++)                         
17             for (j=1;j<=n;j++)
18         {
19             if (j%i==0)
20             {
21                 a[j]=!a[j];
22             }
23         }
24         for (i=1;i<=n;i++)
25             if (a[i]==1)
26             count++;
27         cout << count << endl;
28     }
29 
30     return 0;
31 }

缺点：容易超时，所以转换思路：一开始灯为灭，若有偶数个因子则仍为灭的，所以要想灯亮，灯的序号必须有奇数个因子。

思路二

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int i,j,t,a,n;
 8     long long count;
 9     cin>>t;
10     while (t--)
11     {a=0;count=0;
12         cin>>n;
13         for (i=1;i<=n;i++)
14     for (j=1;j<=i;j++)
15     if (i%j==0)
16         a++;
17         if (a%2!=0)
18         count++;
19     cout << count<< endl;
20     }
21 
22     return 0;
23 }

仍然超时，思考：如果一个数是完全平方数,那么它的因子的个数一定是奇数?
答：X2的因子至少有（1,x,x2，若X2还有因子的话一定是两个不同的数相乘。设还有2n个因子3+2n (n>=0)，所以为奇数。
假设有25盏灯，灯的序号从1到25，25开根号为5，也就是1-5的平方，所以25以内共有5个完全平方数。

正确答案：

 1 #include <iostream>
 2 #include <math.h>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     long long t,n;
 8 
 9     cin>>t;
10     while (t--)
11     {
12         cin>>n;
13 
14     cout << (long long)sqrt(n)<< endl;
15     }
16 
17     return 0;
18 }