P1876 开灯【入门】

客官°小女子只卖身不卖艺 2023-09-28 15:29 5阅读 0赞

[开灯][Link 1]

### 题目描述 ###

首先所有的灯都是关的（注意是关！），编号为  1 1 1 的人走过来，把是  1 1 1 的倍数的灯全部打开，编号为  2 2 2 的人把是  2 2 2 的倍数的灯全部关上，编号为  3 3 3 的人又把是  3 3 3 的倍数的灯开的关上，关的开起来……直到第  N N N 个人为止。

给定  N N N，求  N N N 轮之后，还有哪几盏是开着的。

### 输入格式 ###

一个数  N N N，表示灯的个数和操作的轮数。

### 输出格式 ###

若干数，表示开着的电灯编号。

### 样例 \#1 ###

#### 样例输入 \#1 ####

#### 样例输出 \#1 ####

1 4

### 提示 ###

对于  100 % 100 \\% 100% 的数据， 1 ≤ N ≤ 2 40 1 \\le N \\le 2^\{40\} 1≤N≤240。

思路：（其实巨简单）

因为一开始的灯是关的，如果最后想让灯是开着的情况，那么这个灯的开关就要按奇数次，而如果开关被按了偶数次，那最后还是关着的。

每次开关灯都和倍数有关，如果这个灯的序号是完全平方数，那么它就会被按奇数次，那么最后也就是开的状态；如果序号不是完全平方数，则会被按偶数次，因为当一个数不是完全平方数时，那么它的因子是偶数个，只要有一个数是它的因子，那么用 **这个数** 除 **当前因子** 所得即为该数的另一个因子。

奉上代码（比头文件还短）

#include<iostream>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int a[10001]={
        0};
    
    int main(){
        
        int n;
        cin>>n;
        for(int i=1;i*i<=n;++i)
            cout<<i*i<<" ";
        return 0;
    }

> 其他dalao的思路：（引用一下）

看了看别人的题解，都是枚举小于n的完全平方数输出，代码极为简单，因此本人不再给出代码。

下证明为什么是完全平方数：

首先，你要知道，对于每一个数n，除非它是完全平方数，否则它一定有偶数个因子。

因为如果i是n的因子，那么n/i也一定是n的因子。例如当n=20时，i=4是20的因子，那么n/i=5也是20的因子

这样，n的因子都是成对出现的，所以n有偶数个因子

但是，有一种特殊情况，即n/i=i。例如4/2=2。由于i和n/i是同一个数，算因子只能是一个，这时n的因子就是奇数个

把n/i=i变形，得n=i\*i，即n是完全平方数，所以只有完全平方数有奇数个因子

对于本题，由于灯只有两种状态(开或关,可类比于奇数和偶数),而初始状态是关的

而每个灯泡如果能被人的编号整除，状态就会变化。

把整个过程看成一个整体，也就是只有这一盏灯的因数的编号的人，才会按开关

由于灯的开关按偶数次状态不变，还是关（起始是关），所以，灯的开关只有按奇数次，才会开。