P1876 開燈-有解無憂

洛谷傳送門：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 */

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/518961.html

標籤：其他

上一篇：Codeforces 1684 E. MEX vs DIFF

下一篇：[征途外掛制作記六]