题解

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
bool vis[100000005];
void _init(int n){
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j += i){
            vis[j] = !vis[j];
        }
    }
}
signed main(){
	int n;
	cin >> n;
    _init(n);
    for(int i = 1; i <= n; i++){
        if(vis[i]) cout << i << ' ';
    }

	return 0;
}

不会真有人用这个模拟吧，这个2⁴⁰的数据量O(n)都够呛
那怎么办呢？
我们仔细读题，发现每个灯按开关的次数都是它们所有的因子数
所以我们要找到拥有奇数个因子数的数
但我们发现，如果一个数x有因子y，那它就必然有因子(x/y)等等我好像说过这句话，那怎么可能嘛！
我们再看一下样例，

输出#1
1 4

好像有什么规律……
我们用上面的代码把输入数调大点，如100
输出：

1 4 9 16 25 36 49 64 81 100

……等等，这些数都是完全平方数！！！
没错，完全任意平方数x因为有因子sqrt(x)，而用x除以这个因子竟然还是sqrt(x)！
这样就减少了一个因子，因子数由偶数变成了奇数
所以我们只要输出n以内的完全平方数

#include <iostream>
#include <cstdio>
#define int long long//宏定义
using namespace std;
signed main(){//因为main函数必须返回int类型，所以用signed代替int
	int n;
	cin >> n;
	for(int i = 1; i * i <= n; i++){//遍历n以内完全平方数
		printf("%lld ", i * i);
	}

	return 0;
}

时间复杂度：$O(\sqrt{n})$