hdu 2053 Switch Game 水题一枚，鉴定完毕

Switch Game

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10200 Accepted Submission(s): 6175

Problem Description

There are many lamps in a line. All of them are off at first. A series of operations are carried out on these lamps. On the i-th operation, the lamps whose numbers are the multiple of i change the condition ( on to off and off to on ).

Input

Each test case contains only a number n ( 0< n<= 10^5) in a line.

Output

Output the condition of the n-th lamp after infinity operations ( 0 - off, 1 - on ).

Sample Input

1 5

Sample Output

1 0

Hint

hint

Consider the second test case:

The initial condition : 0 0 0 0 0 …

After the first operation : 1 1 1 1 1 …

After the second operation : 1 0 1 0 1 …

After the third operation : 1 0 0 0 1 …

After the fourth operation : 1 0 0 1 1 …

After the fifth operation : 1 0 0 1 0 …

The later operations cannot change the condition of the fifth lamp any more. So the answer is 0.

Author

转化求n个因子个数，暴力0ms过了(⊙o⊙)…

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 
 7 int num_Euler(int n)
 8 {
 9     int i;
10     int num,ans=1;
11     for(i=2;i*i<=n;i++)
12     {
13         if(n%i==0)
14         {
15             num=1;
16             while(n%i==0)
17             {
18                 n=n/i;
19                 num++;
20             }
21             ans=ans*num;
22         }
23     }
24     if(n!=1)
25         ans=ans*2;
26     return ans;
27 }
28 int main()
29 {
30     int n;
31     while(scanf("%d",&n)>0){
32         int m=num_Euler(n);
33         printf("%d
",(m&1));
34     }
35     return 0;
36 }

View Code

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 
 7 bool dp[100002];
 8 
 9 void init()
10 {
11     int i,j;
12     memset(dp,true,sizeof(dp));
13     for(i=2;i<=100000;i++)
14     {
15         for(j=i;j<=100000;j=j+i)
16             if(dp[j]==true) dp[j]=false;
17             else dp[j]=true;
18     }
19 }
20 int main()
21 {
22     int n;
23     init();
24     while(scanf("%d",&n)>0)
25     {
26         if(dp[n]==false)printf("0
");
27         else printf("1
");
28     }
29     return 0;
30 }

View Code