首页 > 代码库 > hdu 2053 Switch Game 水题一枚,鉴定完毕
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 0Consider the second test case:
Hint
hint 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 }
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。