【GESP】C++二级练习 luogu-B2092, 开关灯

GESP二级练习，多层循环分支嵌套练习，难度★✮☆☆☆。

luogu-B2092 开关灯

题目要求

题目描述

假设有 $N$ 盏灯（$N$ 为不大于 $5000$ 的正整数），从 $1$ 到 $N$ 按顺序依次编号，初始时全部处于开启状态；第一个人（$1$ 号）将灯全部关闭，第二个人（$2$ 号）将编号为 $2$ 的倍数的灯打开，第三个人（$3$ 号）将编号为 $3$ 的倍数的灯做相反处理（即，将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的人都和 $3$ 号一样，将凡是自己编号倍数的灯做相反处理。问当第 $N$ 个人操作完之后，有哪些灯是关闭着的？

输入格式

输入为一行，一个整数 $N$，为灯的数量。

输出格式

输出为一行，按顺序输出关着的灯的编号。编号与编号之间间隔一个空格。

样例输入 #1

10

样例输出 #1

1 4 9

样例输入 #2

5

样例输出 #2

1 4

---

题目分析

1. 初始化所有灯为关着的状态，确保每个灯的初始状态都是关闭的。
2. 将2的倍数编号的灯打开，例如编号为2、4、6等的灯将被打开。
3. 从3开始，依次处理每个数i，将编号为i的倍数的灯的开关状态切换。例如，处理3时，将编号为3、6、9等的灯的状态切换，处理4时，将编号为4、8、12等的灯的状态切换，以此类推。
4. 最终输出所有关着的灯的编号，输出的编号将是最终状态下关闭的灯的编号。

示例代码

#include <iostream>
using namespace std;
int main() {
    int n; // 输入的灯的数量
    cin >> n;
    int arr[n]; // 创建一个大小为n的数组，用于存储每个灯的状态
    for (int i = 0; i < n; i++) {
        arr[i] = false; // 初始化所有灯为关着的状态
    }
    for (int i = 1; i < n; i += 2) {
        arr[i] = true; // 将2的倍数编号的灯打开
    }

    for (int i = 3; i <= n; i++) {
        for (int j = i - 1; j < n; j += i) {
            arr[j] = !arr[j]; // 根据每个数i，切换编号为i的倍数的灯的开关
        }
    }
    for (int i = 0; i < n; i++) {
        if (!arr[i]) {
            cout << i + 1 << " "; // 输出关着的灯的编号
        }
    }
    return 0;
}

还有一种快速算法，就是根据数学运算可以发现，最终关闭态的灯编号都是平方数，因为只有平方数会被操作偶数次，最终保持关闭状态。因此代码如下：

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    for (int i = 1; i * i <= n; i++) {
        cout << i * i << " ";
    
    }
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。