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

[伽莫夫博士]

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

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

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

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

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

关 关 关 关 关 关

第一轮过后：

开 开 开 开 开 开

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

开 关 开 关 开 关

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

开 关 关 关 开 开

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

开 关 关 开 开 开

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

开 关 关 开 关 开

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

开 关 关 开 关 关

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

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

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

[伽莫夫博士]

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整除的灯

稍微改下题目

[伽莫夫博士]

5 分钟前, Tokur 说道:

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

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

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

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

[伽莫夫博士]

1 小时前, shp241 说道:

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

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

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

54 分钟前, soramora 说道:

大佬，这还简单。

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

真的是人均985硕博吗

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

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

[伽莫夫博士]

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;
}
 

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