THE DRUNK JAILER

开关门问题，初始化门（编号1~n）都是关着的，改变状态为开变关、关变开：第1遍，全部改变状态；第2遍，编码2的倍数的门改变状态；第3遍，编码3的倍数的门改变状态

……第n遍，编码n的倍数的门改变状态；

结束后，有多少扇门是开着的

法一：

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int main()
 4 {
 5     int t, n, i, j ;
 6     int a[110] ;
 7     scanf("%d", &t) ;
 8     while(t--)
 9     {
10         scanf("%d", &n) ;
11         memset(a, 0, sizeof(a)) ;//初始化，0代表门关着
12         for(i=1; i<=n; i++)
13         {
14             for(j=1; j<=n; j++)
15             {
16                 if(j%i==0)
17                 a[j] = !a[j] ;//取相反状态
18             }
19         }
20         int count = 0 ;
21         for(i=1; i<=n; i++)
22         {
23             if(a[i]!=0)
24             count++ ;
25         }
26         printf("%d\n", count) ;
27     }
28     return 0 ;
29 }

法二：求约数个数为奇数的数的个数，简单来说就是求n以内（含n）完全平方数的个数

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 int main()
 5 {
 6     int t, n, i, x ;
 7     int a[110] ;
 8     a[5] = 2 ;
 9     for(i=6; i<=100; i++)//打表
10     {
11         x = (int)(sqrt(i)) ;
12         if(x*x==i)
13         a[i] = a[i-1] + 1 ;
14         else
15         a[i] = a[i-1] ;
16     }
17     scanf("%d", &t) ;
18     while(t--)
19     {
20         scanf("%d", &n) ;
21         printf("%d\n", a[n]) ;
22     }
23     return 0 ;
24 }