洛谷传送门:P1876 开灯 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

难度:入门

知识点:数学(因数)

思路:

  第n个灯会被操作多少次,取决与它有多少个因数  比如8,因数有1,2,4,8,有偶数个因数,操作完后是关灯的  比如9,因数有1,3,9,有奇数个因数,操作完后是开着的  因为一个知识点:1以外的自然数,都可以分解为两个自然数的乘积  所以,如果这个数是平方数,他其中的一对因数就是重复的,导致因数的个数变成奇数个  eg:9的因数对有(1,9)(3,3)反思:  虽然打表会超时或者爆内存,但是打表可以帮助我们找出规律  这种一下子想不出需要找规律的题目,可以先打表出来看看,能不能发现规律AC代码:

 1 #include 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 */