T1 题解 - 开关灯

Exam02

题目描述

假设有 $N$ 盏灯，从 $1$ 到 $N$ 按顺序依次编号，初始时全部处于开启状态；有 $M$ 个人也从 $1$ 到 $M$ 依次编号。
第一个人（$1$ 号）将灯全部关闭，第二个人（$2$ 号）将编号为 $2$ 的倍数的灯打开，第三个人（$3$ 号）将编号为 $3$ 的倍数的灯做相反处理（即，将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的人都和 $3$ 号一样，将凡是自己编号倍数的灯做相反处理。
请问：当第 $M$ 个人操作之后，哪几盏灯是关闭的，按从小到大输出其编号，其间用空格间隔。

输入格式

输入正整数 $N$ 和 $M$，以单个空格隔开，$M \le N$。

输出格式

顺次输出关闭的灯的编号，其间用空格间隔。
输出时每行末尾的多余空格，不影响答案正确性

样例输入

10 10

样例输出

1 4 9

数据范围

对于$100\%$的数据，$1 \leq m \leq n \leq 5000$

题解

日常水题：遍历就可以了。
这里$1$号来过之后，所有灯都应该是灭的。
下面S[i]表示第i盏灯是否是亮的。

#include <iostream>
using namespace std;
bool S[5005];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 2; i <= m; ++i) { //begin from 2
        for (int j = 1; j <= n; ++j) {
            if (j % i == 0) S[j] = !S[j]; //reverse
        }
    }
    for (int i = 1; i <= n; ++i) { // output
        if (!S[i]) cout << i << " ";
    }
    cout << endl;
    return 0;
}