首页 > 代码库 > hdu 2053 Switch Game 水题一枚，鉴定完毕

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

2024-07-02 21:44:25   226人阅读

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
LL
 
 
转化求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\n",(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\n");
27         else printf("1\n");
28     }
29     return 0;
30 }
View Code

 

 


联系
我们