开关灯

题目描述

有 $N$ 盏编号 $1\ldots N$ 的灯，初始全部开启。 $M$ 个人按编号从小到大操作：1 号关掉全部灯，2 号打开编号为 2 的倍数的灯， $k\ (k\ge 3)$ 号把 $k$ 的倍数取反。操作完后从小到大输出所有仍然关闭的灯的编号，用逗号分隔。 $N,M\le 5000$ 。样例输入 10 10，输出 1,4,9。

思路

初始全亮让三类操作统一为“第 $k$ 个人翻转 $k$ 的倍数”，无需分支；循环直接落在倍数 $k,2k,3k,\ldots$ 上做异或，总翻转次数即调和级数 $O(N\log M)$ ，最后输出被翻过奇数次的灯。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 19:15
# update_at: 2026-09-29 19:15

import sys


def solve() -> None:
    n, m = map(int, sys.stdin.buffer.read().split())

    # off[j] = 1 表示灯 j 被翻过奇数次（初始全亮，翻奇数次即最终关闭）。
    # 1 号"全部关闭"、2 号"打开 2 的倍数"本质都是取反，统一按翻倍数处理。
    off = bytearray(n + 1)
    for d in range(1, m + 1):
        off[d::d] = bytes(v ^ 1 for v in off[d::d])  # 下标 d, 2d, 3d, ... 恰是 d 的倍数

    print(','.join(map(str, (j for j in range(1, n + 1) if off[j]))))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 01:40
 * update_at: 2026-10-05 01:40
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 5005;

int n, m;
// off[j] = 1 表示灯 j 被翻过奇数次（初始全亮，翻奇数次即最终关闭）。
int off[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;

    // 1 号"全部关闭"、2 号"打开 2 的倍数"、k>=3 号"取反 k 的倍数"，
    // 三类操作在"初始全亮"下都等价于：把该人编号的倍数翻转一次。
    // 循环直接落在倍数上，省掉 j % k == 0 的逐灯判断。
    for (int d = 1; d <= m; d++) {
        for (int j = d; j <= n; j += d) {
            off[j] ^= 1;
        }
    }

    bool first = true;
    for (int j = 1; j <= n; j++) {
        if (off[j]) {
            if (!first) cout << ',';
            cout << j;
            first = false;
        }
    }
    cout << '\n';
    return 0;
}

目录

题目描述

思路

参考代码