娱乐 【算法挑战——2022年第一期】开关灯泡

[shp241]

由于1-n每一盏灯都会被按所以事实上m号灯最终是暗还是灭仅取决于其因数个数……因数个数为奇则最后为亮，因数个数为偶则最后为灭

至于因数个数奇偶我不知道，于是去算了100以内的数的因数个数，最后发现仅平方数为奇数，所以大胆假设n盏灯最后亮灯数为包含的平方数个数，即 ⌊√n⌋

[shp241]

1 分钟前, Tokur 说道:

并不是仅仅平方数的因数是奇数啊x  所有的偶数殆素数的都是奇数啊x，例如2殆素数 15=3*5*1

1，3，5，15，是有4个因数的

我确实去算了：

剧透

1 1
2 2
3 2
4 3
5 2
6 4
7 2
8 4
9 3
10 4
11 2
12 6
13 2
14 4
15 4
16 5
17 2
18 6
19 2
20 6
21 4
22 4
23 2
24 8
25 3
26 4
27 4
28 6
29 2
30 8
31 2
32 6
33 4
34 4
35 4
36 9
37 2
38 4
39 4
40 8
41 2
42 8
43 2
44 6
45 6
46 4
47 2
48 10
49 3
50 6
51 4
52 6
53 2
54 8
55 4
56 8
57 4
58 4
59 2
60 12
61 2
62 4
63 6
64 7
65 4
66 8
67 2
68 6
69 4
70 8
71 2
72 12
73 2
74 4
75 6
76 6
77 4
78 8
79 2
80 10
81 5
82 4
83 2
84 12
85 4
86 4
87 4
88 8
89 2
90 12
91 4
92 6
93 4
94 4
95 4
96 12
97 2
98 6
99 6
100 9

至于原因我不知道，猜测是因为普通的因数加进去就会是两个，但如果是平方数就两个合并成一个所以成奇数了什么的（

一月 23, 2022，由shp241修改

[shp241]

1 分钟前, 伽莫夫博士 说道:

答案正确，不过希望能解释下为什么只有平方数因数为个数

这题频率还挺高的，所以我感觉有不少人会看过答案……

我做题都是一般这样找规律做（

至于为什么我思考一下……

定理：对于一个数a，将其分解质因数，相同的质因数写成幂指数的形式，就是所有质因数的幂指数都加1后，相乘的积。

如96=2^5*3^1

则其因数个数为(5+1)*(1+1)=12个

想要因数个数为奇数，则连乘式中每一个括号需要均为奇数，则+1之前均为偶数，意味着数a的所有质因数的幂均为偶数次幂，则其为完全平方数

[shp241]

11 分钟前, 伽莫夫博士 说道:

答案正确，不过希望能解释下为什么只有平方数因数为个数

这题频率还挺高的，所以我感觉有不少人会看过答案……

还没刷leetcode（

不过我感觉这题这样做的话和算法也没啥关系了……单纯的数学问题，要做算法的话打表就行了