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

[伽莫夫博士]

今年第一题，出个简单的。楼主租的房正好灯泡坏了，特出此题。

楼主这里有n个灯泡排成一行。按下一个灯泡的开关，这盏灯打开，再按下这个开关，灯关闭。

一开始每盏灯都是关闭的。第一轮，楼主按下所有灯泡的开关，然后第二轮，楼主从第一个灯泡开始计数，每两个灯泡按下第二个灯泡的开关，第三轮每三个灯泡按下第三个灯泡的开关，依此类推，第i轮按下所有编号能被i整除的灯泡的开关（1≤i≤n）。第n轮之后，楼主就无开关可按了。

如果光这么说不清楚，下面举一个例子。

假设n=6即有六个灯泡，最初是全部关闭的：

关 关 关 关 关 关

第一轮过后：

开 开 开 开 开 开

第二轮过后（按下第246盏灯的开关）：

开 关 开 关 开 关

第三轮过后（按下第36盏灯的开关）：

开 关 关 关 开 开

第四轮过后（按下第4盏灯的开关）：

开 关 关 开 开 开

第五轮过后（按下第5盏灯的开关）：

开 关 关 开 关 开

第六轮过后（按下第6盏灯的开关）：

开 关 关 开 关 关

问：n轮过后，n盏灯总共有多少盏开着？

参数：只有正整数n，如果当作编程题，可以认为1≤n≤10^8

一月 23, 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修改

[万人毒]

算法怎么变态吗  我幸好我是安全项的  

[伽莫夫博士]

6 分钟前, Tokur 说道:

可以发现，第一轮操作相当于取非，而6轮重复一次操作，故可以发现7-12轮与1-6轮会相互抵消(列举也可以发现12论为000000)，不妨设n轮后有f(n)盏灯开着，故有f(n+12)=f(n),故其周期为12，直接列举拟合x
f(1)=6
f(2)=3
f(3)=3
f(4)=4
f(5)=3
f(6)=2
f(7)=4
f(8)=3
f(9)=3
f(10)=2
f(11)=1
f(12)=0

拉格朗日插值法得到1305 - (3563239 x)/924 + (39702353 x^2)/8400 - (971732609 x^3)/302400 + (7716211 x^4)/5670 - (13132297 x^5)/34560 + (12414953 x^6)/172800 - (932359 x^7)/100800 + (96577 x^8)/120960 - (10691 x^9)/241920 + (5141 x^10)/3628800 - (19 x^11)/950400

故f(n)=1305 - (3563239 x)/924 + (39702353 x^2)/8400 - (971732609 x^3)/302400 + (7716211 x^4)/5670 - (13132297 x^5)/34560 + (12414953 x^6)/172800 - (932359 x^7)/100800 + (96577 x^8)/120960 - (10691 x^9)/241920 + (5141 x^10)/3628800 - (19 x^11)/950400,其中x=n mod 12,n∈N+

暴力破解x

（当然其实插值并没有必要x ）

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

稍微改下题目

[Tokur]

刚刚, 伽莫夫博士 说道:

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

稍微改下题目

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

一月 23, 2022，由Tokur修改

[伽莫夫博士]

5 分钟前, Tokur 说道:

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

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

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

一月 23, 2022，由伽莫夫博士修改

[Tokur]

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

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

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

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

[shp241]

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

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

[Tokur]

4 分钟前, shp241 说道:

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

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

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

[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修改

[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

[soramora]

大佬，这还简单。

leetcode是就有这道算法题，做到过，没做出来。

真的是人均985硕博吗

一月 23, 2022，由soramora修改

[伽莫夫博士]

1 小时前, shp241 说道:

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

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

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

54 分钟前, soramora 说道:

大佬，这还简单。

leetcode是就有这道算法题，做到过，没做出来。

真的是人均985硕博吗

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

一月 23, 2022，由伽莫夫博士修改

[愚昧者]

#include<stdio.h>
#define N 6
#define MAXN 100000001

 

int main(){

    int lamp[MAXN],i,j,answer;

    for(i=1;i<=N;i++)lamp[i]=0;

 

    for(i=1;i<=N;i++)for(j=i;j<=N;j+=i){

        if(lamp[j]==0)lamp[j]=1;

        else lamp[j]=0;

    }

 

    answer=0;

    for(i=1;i<=N;i++)if(lamp[i]==1)answer++;

    printf("%d\n",answer);

 

    return 0;
}
 

[starch]

题目可以转换为求n以内的因数个数为奇数个的数有多少。

假设质因数分解后有k个质因数，分别出现了ei次，则

因数个数为(e1+1)*(e2+1)*(e3+1)*……（ek+1）

因数个数要为奇数，则所有质因数均出现偶数次，显然为平方数，所以sqrt(n)求n以内平方数即可。

我怎么感觉我见过这题。（

[shp241]

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

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

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

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

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

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

如96=2^5*3^1

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

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

[shp241]

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

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

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

还没刷leetcode（

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

[starch]

5 分钟前, starch 说道:

题目可以转换为求n以内的因数个数为奇数个的数有多少。

假设质因数分解后有k个质因数，分别出现了ei次，则

因数个数为(e1+1)*(e2+1)*(e3+1)*……（ek+1）

因数个数要为奇数，则所有质因数均出现偶数次，显然为平方数，所以sqrt(n)求n以内平方数即可。

我怎么感觉我见过这题。（

对了，sqrt(n)应该加个下取整。（

[伽莫夫博士]

4 分钟前, starch 说道:

题目可以转换为求n以内的因数个数为奇数个的数有多少。

假设质因数分解后有k个质因数，分别出现了ei次，则

因数个数为(e1+1)*(e2+1)*(e3+1)*……（ek+1）

因数个数要为奇数，则所有质因数均出现偶数次，显然为平方数，所以sqrt(n)求n以内平方数即可。

我怎么感觉我见过这题。（

 

2 分钟前, shp241 说道:

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

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

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

如96=2^5*3^1

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

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

到这里可以说是完美了。

我自己的证法是，对于正整数x的任意因数a，正整数b = x / a必定也是x的因数。

因此对于所有x的小于sqrt(x)的因数a1，a2，a3……，必定存在b1，b2，b3……满足bi = x / ai且bi是x的因数且bi > sqrt(x)。

集合{ai}的元素个数显然等于集合{bi}的元数个数。x为非平方数时，{ai}∪{bi}就是所有因数了，其个数显然为偶数。

x为平方数时，还要加上一个sqrt(x)，此时个数为奇数。

[伽莫夫博士]

18 分钟前, 愚昧者 说道:

#include<stdio.h>
#define N 6
#define MAXN 100000001

 

int main(){

    int lamp[MAXN],i,j,answer;

    for(i=1;i<=N;i++)lamp[i]=0;

 

    for(i=1;i<=N;i++)for(j=i;j<=N;j+=i){

        if(lamp[j]==0)lamp[j]=1;

        else lamp[j]=0;

    }

 

    answer=0;

    for(i=1;i<=N;i++)if(lamp[i]==1)answer++;

    printf("%d\n",answer);

 

    return 0;
}
 

这个数据范围应该会超时的

[fangaa]

只有平方数的因数是奇数个，这好像是学奥数的时候提到的。

[Jerryxxw]

好家伙，怎么还能在这儿看到力扣题

除了完全平方数其他数的因数都是成对的，一开始状态是关，问的是开灯泡数，那就是n中完全平方数的个数

[水墨潇潇]

草 感觉脑子不够用