问题解决策略数据类型实现训练2

问题 F: 捣乱的守望

题目描述

L老师有 NNN 盏灯（NNN ≤\le≤ 300030003000 ），从 111 到 NNN 按顺序依次编号，初始时全部处于开启状态。守望很淘气，他想捉弄一下L老师，于是进行了 NNN 次操作。在第一次操作时将灯全部关闭，第二次操作将编号为 222 的倍数的灯打开，第三次操作将编号为 333 的倍数的灯做相反处理（即将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的操作都是将编号倍数的灯做相反处理。L老师知道后很是烦恼，因此他想让你计算出哪些灯最终是关闭状态。

输入

输入为一行，一个整数 NNN，为灯的数量。

输出

输出为一行，按顺序输出关着的灯的编号。编号与编号之间间隔一个空格。

输入输出样例

样例输入 #1

复制

10

样例输出 #1

复制

1 4 9

样例输入 #2

复制

5

样例输出 #2

复制

1 4

看测试用例猜了平方数，真猜对了。

#include<iostream> #include<cmath> //看测试用例找规律发现的 using namespace std; int main() { int n; cin >> n; int en = sqrt(n); for (int i = 1;i <= en;i++) cout << i * i << " "; return 0; }

为什么是平方数：

• 一个数k被操作的次数等于它的因数个数

• 只有平方数有奇数个因数

• 证明：对于非平方数n，因数总是成对出现的（如12的因数对：1×12, 2×6, 3×4），所以有偶数个因数

• 对于平方数n = a²，因数对中会有一个重复的（如9的因数对：1×9, 3×3），所以有奇数个因数

因此：

• 平方数会被操作奇数次，最终状态是关闭

• 非平方数会被操作偶数次，最终状态是开启