筛法

可以注意到：将 $i$ 分解因式后得到的因数个数为奇数，那么第 $i$ 个灯就是亮的，所以我们按着这个思路筛。

所以借助埃筛的思想，我们记录每次遍历到 $j$ 的次数，这个次数就是它的因数的个数。

注意我们要初始化数组的值为 $1$

时间复杂度为 $O(n\log n)$

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;

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

	int n;
	std::cin >> n;

	std::vector<int> f(n + 1, 1);
	for (int i = 2; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			f[j]++;
		}
	}

	for (int i = 1; i <= n; i++) {
		if (f[i] & 1) {
			std::cout << i << " ";
		}
	}

	return 0;
}

可以直接模拟开关灯，每次对灯的状态取反即可，但是数据如果大了，就无法成功通过题目。

对于一盏灯，一开一关为 $2$ 次，所以经过偶数次开关，灯的状态不会变。对任意一个小于 $N$ 的正整数 $x$，只有因数个数为奇数时，才能让灯由关到开。而对于 $x$ 的任意一个因数i，总存在因数 $\frac xi$ 。若 $i \neq \frac xi$，那么 $x$ 的因数个数就为偶数；相反，若 $i = \frac xi$时，即 $x = i^2$，$x$ 的因数个数就为奇数，此时，$x$ 就是一个完全平方数。所以只需从 $1$ 到 $N$ 枚举完全平方数就可以了。

#include <bits/stdc++.h>

int main()
{
	int n;
	std::cin >> n;
	for (int i = 1; i*i <= n; i ++) {
		std::cout << i * i << ' ';
	}
	return 0;
}