HDU 2053 Switch Game(基础题)

一开始做这道题的时候还是想用了用三原色的那种方法来做了一下，果然，超时了，看如下代码：

#include 
  
   
#include 
   
     #include 
     
     using namespace std
     ; int Kesha
     [100005
     ]; int main() { int n
     ; while(~scanf
     (%d
     , &n
     )) { memset
     (Kesha
     , 0
     , sizeof(Kesha
     )); for(int i
     =1
     ; i
     <=n
     ; i
     ++) { for(int j
     =1
     ; j
     <=n
     ; j
     ++) { if(j
      % i
      == 0
     ) { Kesha
     [j
     ] = !Kesha
     [j
     ]; } } } printf
     (%d 
     , Kesha
     [n
     ]); } } 
    
   
  

后来想了想，就用了另外一种解三原色类的题目做：就是用最大公约数和最小公倍数的方法， 比如说输入一个n = 4，他的约数有1， 2， 4 为奇数个； n = 5, 约数有1, 5 为偶数个；这时候差不多规律就出来了，只要统计n的约数的个数是奇数还是偶数，即可判断第n盏灯是亮的还是关闭的；

解题代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
      
      using namespace std
      ; int Kesha
      [100005
      ]; int main() { int n
      ; while(~scanf
      (%d
      , &n
      )) { if(n
       == 1
      ) { //边界：当n==1时，状态应为1； printf
      (1 
      ); continue; } int count
       = 0
      ; //设置一个计数器count； for(int i
      =2
      ; i
      <=n
      /2
      ; i
      ++) { //只要判断不超过n/2的约数有几个； if(n
       % i
       == 0
      ) { count
      ++; } } if((count
      +2
      ) % 2
       == 0
      ) { 当为偶数时，灯是关闭的； printf
      (0 
      ); }else { printf
      (1 
      ); //奇数时灯是亮着的； } }
     
    
   
  

}