面试题38：灯的状态

问：对一批编号为1～100全部开关朝上开的灯进行以下操作，凡是1的倍数反方向拨一次开关；2的倍数反方向再拨一次开关；3的倍数反方向再拨一次开关。那最后为关闭状态的灯的编号是多少？

答：根据题目我们可以知道，号码为N的灯，拨开关的次数等于N的约数的个数。

要想使灯关闭，约数的个数应该是奇数。

而一般来说，任何一个数N都至少有两个约数，即1和N本身。

其他任何一个约数都是一一对应的（例如6的约数中2和3对应）。

从理论上来讲，每个数的约数的个数都应该是偶数。

只有一种例外的情况，即某数中两个互相对应的约数相等，例如4的约数中2的对应约数也为2。

这样的数才能有奇数个约数。

即N必须为某数的平方。

100以内最大的平方数为100，即10的平方。

最小的平方数为1，即1的平方。

那么100以内的平方数总共只能有10个，如下所示。

1²=1

2²=4

3²=9

4²=16

5²=25

6²=36

7²=49

8²=64

9²=81

10²=100

而这些平方数就是所求的编号数。