思路与算法

建立下标1到n的布尔数组，初始全关。依次处理服务员i，把i、2i、3i等不超过n的房门取反。最后按编号递增输出打开的门。第一轮翻转所有门，正好完成第一个服务员的开门动作。标程完整模拟，平方数性质只用来独立核验。

正确性说明

第i轮前数组表示前i-1位服务员的真实操作结果。内层循环恰好遍历第i位服务员负责的倍数门，各取反一次，所以本轮后仍与实际状态一致。初始全关正确，由归纳得n轮后的数组准确，输出所有真值项就是答案。独立核验：编号k被翻转约数个数次，约数成对，只有平方数的约数个数为奇数，所以打开的门为完全平方数。所有n=2至1000的模拟均已与平方数序列对照。

复杂度

数组初始化与最终扫描O(n)，所有翻转次数为sum(floor(n/i))=O(n log n)，总时间O(n log n)，额外空间O(n)。n不超过1000。

易错点

初始全关，第一位负责全部打开；只输出打开的门。输出用空格。不能套用输入N和M、初态全开、要求关闭灯且逗号输出的另一版本。

参考代码（C++11）

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<bool> open(n + 1, false);
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i)
            open[j] = !open[j];
    bool first = true;
    for (int i = 1; i <= n; ++i)
        if (open[i]) {
            if (!first)
                cout << ' ';
            cout << i;
            first = false;
        }
    cout << '\n';
}