每日一题：100 doors

选自100 doors - Rosetta Code

Task

There are 100 doors in a row that are all initially closed.You make 100 passes by the doors.The first time through, visit every door and toggle the door (if the door is closed, open it;if it is open, close it).The second time, only visit every 2nd door(door #2, #4, #6, …),and toggle it.The third time, visit every 3rd door(door #3, #6, #9, …), etc,until you only visit the 100th door. Answer the question: what state are the doors in after the last pass? Which are open, which are closed?

Solution

最先想到的办法就是两层循环仿真一遍，时间复杂度是O(nlogn)，推导如下：

n + n/2 + n/3 + n/4 + … + n/n = n(1+1/2+1/3+1/4+…+1/n) = n(ln(n+1)+r)

欧拉近似地计算了r的值，约为0.577218，这个数字后来称作欧拉常数。 但换个角度，第m扇门，如果有a,b < m且a*b=m，那么一开一关互相抵消，以6为例，会在1、2、3，6发生翻转，显然6=1*6=2*3，但对于可以开方的数，比如9=1*9=3*3，会在1、3、9发生翻转，由于3重复了，所以相当于执行了一次翻转。因此如果m可以开方，则开着；不可以开方，则关着。

Implementation