77-开灯问题

题目描述:

有n盏灯，编号为1~n，第1个人把所有灯打开，第2个人按下所有编号为2 的倍数的开关（这些灯将被关掉），第3 个人按下所有编号为3的倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），依此类推。一共有k个人，问最后有哪些灯开着？输入：n和k，输出开着的灯编号。k≤n≤1000

输入描述:

输入一组数据：n和k

输出描述:

输出开着的灯编号

样例输入:

复制

7 3

样例输出:

1 5 6 7

分析：
　　1、通过数组存原先的状态；
　　2、以其倍数关系遍历数组，改变该位置的状态

C/C++代码实现（AC）：

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <stack>

 #include <map>

 #include <queue>

 #include <set>

 using namespace std;

 const int MAXN = ;

 int f[MAXN] = {};

 int main()

 {

     int n, k;

     scanf("%d%d", &n, &k);

     for (int i = ; i <= k; ++ i)

     {

         for (int j = i; j <= n; j += i)

         {

             if (f[j] == ) f[j] = ;

             else f[j] = ;

         }

     }

     for (int i = ; i <= n; ++ i)

         if (f[i])

             printf("%d ", i);

     return ;

 }

巴特西

nyoj 77-开灯问题 (倍数遍历)

77-开灯问题

题目描述:

输入描述:

输出描述:

样例输入:

样例输出:

最新文章

热门文章