洛谷传送门：P1876 开灯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
难度：入门
知识点：数学（因数）
思路：
第n个灯会被操作多少次，取决与它有多少个因数 比如8，因数有1，2，4，8，有偶数个因数，操作完后是关灯的 比如9，因数有1，3，9，有奇数个因数，操作完后是开着的 因为一个知识点：1以外的自然数，都可以分解为两个自然数的乘积 所以，如果这个数是平方数，他其中的一对因数就是重复的，导致因数的个数变成奇数个 eg：9的因数对有（1，9）（3，3） 反思： 虽然打表会超时或者爆内存，但是打表可以帮助我们找出规律 这种一下子想不出需要找规律的题目，可以先打表出来看看，能不能发现规律 AC代码： 1 #include<bits/stdc++.h>
2 using namespace std;
3
4 int main(){
5 int n; scanf("%d", &n);
6 for(int i = 1; i*i<=n; i++){
7 printf("%d ",i*i);
8 }
9 }
10
11 int main01(){ //打表
12 int n; scanf("%d", &n);
13 vector<int> arr(n+1,1);
14 for(int i = 2; i<=n; i++){
15 for(int j = 1; j<=n; j++){
16 if(j%i==0) arr[j] *= -1;
17 }
18 }
19 for(int i = 1; i<=n; i++){
20 if(arr[i]==1)
21 printf("%d ",i);
22 }
23 return 0;
24 }
25
26 /*
27 知识点：数学（因数）
28
29 心路历程：
30 直接模拟，爆内存了
31 隐隐约约觉得存在什么规律
32
33 看题解说是平方数，这题的价值在与证明为什么是输出平方数
34 第n个灯会被操作多少次，取决与它有多少个因数
35 比如8，因数有1，2，4，8，有偶数个因数，操作完后是关灯的
36 比如9，因数有1，3，9，有奇数个因数，操作完后是开着的
37 因为一个知识点：1以外的自然数，都可以分解为两个自然数的乘积
38 所以，如果这个数是平方数，他其中的一对因数就是重复的，导致因数的个数变成奇数个
39 eg：9的因数对有（1，9）（3，3）
40
41 反思：
42 虽然打表会超时或者爆内存，但是打表可以帮助我们找出规律
43 这种一下子想不出需要找规律的题目，可以先打表出来看看，能不能发现规律
44
45 */
标签：P1876,洛谷,知识点,int,开灯,因数 From： https://www.cnblogs.com/--OvO--/p/16815673.html