100个门的打开与关闭问题

  第一次,操作门1,2,3,4,...,100

  第二次,操作门2,4,6,8,...,100

  第三次,操作门3,6,9,12,...,99

  第4次,操作门4,8,12,16,...,100

  ...

  第100次,操作门100

  上面操作的意思是:如果原来门市open的,就关掉它;如果原来是closed的,就打开它。第100次之后,哪些门市open的,哪些men是closed的。

解答:每一次操作都是操作门号可以整除操作序号的门(即操作序号是门号的因子),可见一个门被操作的次数等于其因子数,例如15被操作4次:分别是1,3,5,15次。

     可见,门最后的开关跟门号有几个因子有关,因子数为奇数则为开,因子数为偶数则为关。

    那么什么什么数由奇数个因子呢?例如36,它的因子有(1,36),(2,18),(3,12),(4,9),(6,6)。注意(6,6)只仅仅贡献1个因子,从而使得36有奇数个因子。

    因此一个数只要不是某个数的平方,即两两配对,则必然有偶数个因子,若为某个数的平方必定为奇数个因子,所以1,4,9,16,25,36,49,64,81,100为open,其余为close。

原文地址:https://www.cnblogs.com/vincently/p/4827801.html