algorithm - 为什么这里会出现这种数学模式？

Question

实际问题是这样的

A room has N (1 to N inclusive) bulbs and N switches. N people go in one by one. 1st person goes in and toggles none of the switches. 2nd person goes in and toggles all switches other than the multiples of 2(2, 4, 6...). 3rd person goes in and toggles all switches other than multiples of 3(3, 6, 9...), and so on (Till Nth person toggles all the switches except Nth switch). Once the process is finished, how many bulbs are in 'on' state. (Assume that all bulbs to be in 'off' state initially).

原题可查here

我试着先写一个强力求解器来解决它，但它会给我一个“超过时间限制”的结论，因为 N 可以大到 10E9，

在测试某些 N 值的解决方案时，我偶然发现了一个导致最终解决方案的模式

最好用图片来解释，观察由 0 分隔的 1 的数量 - 2 , 4 , 6 , 8 ...

但我还是想不通为什么会存在这种模式？换句话说，这种模式背后的数学原因是什么？

这是我使用的draw(N)代码

def draw(N):
    arr=[0]*N
    for i in range(2,N+1):
        for j in range(0,N):
            if((j+1)%i!=0):
                arr[j]^=1
    print(N,arr)
    ans=0
    for i in range(0,N):
        if(arr[i]==1):
            ans+=1
    print(ans)

Answer 1

这是一个 old puzzle 的版本.通常的版本是让第 n 个人翻转数字可被 n 整除的开关，并产生相同的方 block 图案(方 block 索引为 1、4、9、16 的开关被切换)，无论 N 是偶数还是奇数。在这里，恰好相反的开关被切换，这相当于将所有开关额外切换 N 次，如果 N 是偶数则什么都不做，而当 N 是奇数时反转它们。您只展示了 N 为奇数的情况，这意味着方 block 是不改变状态的开关。

一个数的因数成对出现，除非该数是正方形，因为我们可以将因数 x 与 n/x 配对，并且它们是不同的，除非 x^2=n。

例如，18 有 6 个因数:1 和 18、2 和 9 以及 3 和 6。因此，如果您为每个因数拨动开关 18 一次，它会保持其原始状态。

100 有 9 个因子:1 和 100、2 和 50、4 和 25、5 和 20，以及 sqrt(100)=10。因此，如果您为每个因素切换开关 100 一次，它会改变状态。

您提到了 0 之间 1 的数量。 (n+1)^2-n^2 = 2n+1。因此，对于 N 个奇数，您会在 0 之间看到 2、4、6、8 等 1。