为什么这个数学模式出现在这里？

Question

实际问题是这样的

房间有N(1到N个)灯泡和N个开关.N个人一个接一个地进去.第一个人进去切换没有开关.第二个人进入并切换除2的倍数之外的所有开关(2,4,6 ......).第3个人进入并切换除3的倍数(3,6,9 ......)之外的所有开关,依此类推(直到第N个人切换除第N个开关之外的所有开关).一旦完成该过程,有多少个灯泡处于"开启"状态.(假设所有灯泡最初处于"关闭"状态).

原始问题可以在这里找到

我试着先写一个暴力解算器来解决它,但它会给我一个"超出时间限制"的判决,因为N可以和10E9一样大,

在测试N的某些值的解决方案时,我找到了导致最终解决方案的模式

最好用图片解释,观察1的数字,用0分隔 - 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

这是旧拼图的一个版本.通常的版本让第n个人翻转其数字可被n整除的开关,并产生相同的正方形图案(方形索引1,4,9,16的开关被切换),无论N是偶数还是奇数.在这里,恰好相反的开关被切换,这相当于将所有开关额外切换N次,如果N是偶数则不执行任何操作,并且当N为奇数时反转它们.您只显示N为奇数的情况,这意味着正方形是不改变状态的开关.

数字的因子成对出现,除非数字是正方形,因为我们可以将因子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,4和6,8等1为N奇数.