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

[Tokur]

尬住了x  题目似乎理解错了mm

---

剧透

以下是题目修改后的算法（正在算x）

对单个灯泡进行研究(灯泡存在的情况下)，容易证明:

1最后必然开着(1=1)，因数为1
2最后必然关着(2=1*2),因数为1,2
3最后必然关着(3=1*3)因数为1,3
4最后必然开着(4=2*2*1)因数为1,2,4
5最后必然关着(5=1*5)因数为1,5
6-0-6=1*2*3-1,2,3,6

······

可以发现，一个灯泡最后的开闭，取决于其质因数分解后的因数个数，若为奇数则必然开着，若为偶数则必然关着,那现在考虑一个数其质因数个数

嗯，先咕了x  查查文献有没有什么好用的定理(bushi

诶！已经有人解出来了嘛x  权当是学习吧x

一月 23, 2022，由Tokur修改

[Tokur]

刚刚, 伽莫夫博士 说道:

嗯……并不是6轮一循环，而是第m轮按下n盏灯中编号能被m整除的灯

稍微改下题目

诶，这样子的嘛，那其实算法也差不多x 不过题目没给参数m诶x  

一月 23, 2022，由Tokur修改

[Tokur]

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

如果灯泡数量是n，总共要按n轮，第m轮按下n盏灯中所有编号能被m整除的灯的开关，1<m<n

显然，不需要按第n+1轮，因为灯的编号从一开始，不存在编号能被n+1整除的灯了，所以总共按n轮

草，咱以为是参数写重了x

[Tokur]

4 分钟前, shp241 说道:

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

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

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

[Tokur]

刚刚, shp241 说道:

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

 

等等草  这波又是咱憨批了x