题意
有 N 盏灯，开始全关。
第 i 个人会把所有编号是 i 的倍数的灯切换一次状态。
问最后哪些灯是亮着的。
思路
先看一个可以直接验证想法的朴素解：
小数据时可以直接模拟每一轮翻灯。
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> on(n + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i) {
on[j] ^= 1;
}
}
bool first = true;
for (int i = 1; i <= n; i++) {
if (!on[i]) continue;
if (!first) cout << ' ';
cout << i;
first = false;
}
cout << '\n';
return 0;
}关键观察是：编号为 x 的灯会在 x 的每个约数那一轮被翻一次，所以它总共被翻的次数等于 x 的约数个数。
非完全平方数的约数成对出现，约数个数是偶数，最后还是灭的。 只有完全平方数在根号处没有成对约数，因此约数个数是奇数，最后会亮。
所以答案就是所有不超过 N 的完全平方数。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
bool first = true;
for (long long i = 1; i * i <= n; i++) {
if (!first) cout << ' ';
cout << i * i;
first = false;
}
cout << '\n';
return 0;
}复杂度
只需要枚举到
总结
这题的本质不是模拟，而是发现“亮灯编号 = 完全平方数”这个数学结论。