问题解决策略数据类型实现训练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看测试用例猜了平方数真猜对了。#includeiostream #includecmath //看测试用例找规律发现的 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所以有奇数个因数因此平方数会被操作奇数次最终状态是关闭非平方数会被操作偶数次最终状态是开启