切换到N的灯的算法是什么？

Question

我今天在一次面试中遇到了这样的情况，我完全不知所措。下面是对这个问题的描述：

房间里有一组从1到100的灯，还有100个人。第一个人走进房间，打开所有编号为i的灯。如果那个灯已经亮了，他们就会把它关了(也就是说，他们会打开灯)。100只是随机数--解应该达到任意值N (N，==数，灯数，==数，人数)。

例如，person 1会打开所有的灯(因为每个数字都是1的倍数)。Person 2将切换2的倍数(2、4、6、8等)的所有灯。这将持续到第100个人。

当时，我觉得这可能与试图确定N的素数有关，但我不能100%确定，所以我采用了一种蛮力方法(以下是我在PHP中提供的大致内容)：

function lights_toggled($number_of_lights) {
  $toggly = function($idx, $lights) {
    foreach($lights as $i => $light) {
      if($i % $idx == 0) {
        if($lights[$i]) {
          $lights[$i] = 0;
        } else if(!$lights[$i]) {
          $lights[$i] = 1;
        } 
      } 
    } 
    return $lights;
  };

  $lights = array_fill(1,$number_of_lights,0);
  for($i = 1; $i <= count($lights); $i++) {
    $lights = $toggly($i, $lights);
  }
  return array_sum($lights);
}

我觉得一切都很好，直到我回到家，开始观察这个函数的输入和输出。我这样做是为了得到一些样本结果：

$results = array();
for($j = 1; $j <= 100; $j++) {
  $number_of_lights_on = lights_toggled($j);
  $results[$number_of_lights_on][] = $j;
}
print_r($results);

它很长，所以这里有一个输出片段，用于== 3或4上的灯光#：

...
[3] => Array
    (
        [0] => 9
        [1] => 10
        [2] => 11
        [3] => 12
        [4] => 13
        [5] => 14
        [6] => 15
    )

[4] => Array
    (
        [0] => 16
        [1] => 17
        [2] => 18
        [3] => 19
        [4] => 20
        [5] => 21
        [6] => 22
        [7] => 23
        [8] => 24
    )
...

当灯的数目在9到15之间时，答案是3盏灯。当灯的数目在16到24之间时，答案是4盏灯。基本上，当x光返回时，总光数的下界是x^2，它的上限是x(x+2)。

我开始看到这里的结构，但我不能用手指来判断这个结果是否遵循一个我不记得或不知道的算法。

Answer 1

这个问题被经典地称为“锁定问题”--网上对这个问题有很多解释，比如这个：

链接

它的主旨是有偶数个除数的人最终会处于他们的起始状态，而那些有奇数除数的人最终会处于相反的状态。这与是否是质数并没有多大关系，尽管除法者在很大程度上考虑到了这一点。

特别是有奇数的除数的数字都是.鼓声..。完美的方块。因为除平方根以外的任何其他除数都会有一个匹配的和不相等的除数，但是完美的平方有一个额外的除数(平方根)，它不会与另一个除数配对；它与自己成对。

请注意，对于特定的问题(有多少是打开的)，这意味着对于N灯，答案将是N，因为有多少个完美方格小于或等于N。