2039 - 开灯关灯
有n盏等，编号为1~n，第1个人把所有灯打开，第2个人按下所有编号为2的倍数的开关（这些灯将被关掉），第3个人按下所有编号为3的倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），以此类推。一共有k个人，问最后有哪些灯开着？
Input
输入数据有多组，输入n盏灯以及k （k≤n≤1000）
Output
输出开着的灯的编号，参照样例输出
Examples
Input
7 3 8 2
Output
1 5 6 7 1 3 5 7
Solution C
#include<stdio.h> #include<string.h> main() { int num[1001],n,k; while(scanf("%d%d", &n, &k)!=EOF) { memset(num,0,sizeof(int)*1001);//0开1关 int i,j; for(i=2;i<=k;i++) { for(j=1;j<=n;j++) if(j%i==0) { if(num[j]==0) num[j]=1; else num[j]=0; } } for(i=1;i<=n;i++) { if(num[i]==0) printf("%d\n",i); } } }
Solution C++
#include<stdio.h> #include<string.h> int lamp[101]; int main() { int n , k , i , j; while(scanf("%d%d",&n,&k)!=EOF) { memset(lamp,0,sizeof(lamp)); for(i =2 ; i <= k ; i++) { for(j = 1 ; j * i <= n ;j++) { if(lamp[i*j] == 0) lamp[i*j] = 1; else lamp[i * j] = 0; } } for(i = 1 ; i <= n ; i++) { if(lamp[i] == 0){ printf("%d",i); printf("\n"); } } } }