关于求含有奇数个因素的数的面试题

最近遇到的一个面试题目：

依次排列有1-k号的门，门有两种状态：开或关，初始状态都为关。然后一个人手里有k张牌，上面依次标有1-k的数字，现在这个人依次拿手中的牌上得数字去除k个门上的号码，如果能整除，则将门的状态改变，即由关变为开，或由开变为关，问最后门的状态分别是什么？

 

 

分析问题：对于每一扇门，将门号分别除以1-k中的每一个数，如果能整除，则门的状态变一次，其实就是求1-k中有多少个数是该门号的因数，例如，k取30，对于20号门，1-30中能整,20的数包括1,20，2,10,4,5，为6个，偶数个则门的状态不变，对于16号门，1-30中能整除16的数包括1,16,2,8,4，为奇数个，则16号门的状态改变。

通过列举发现规律：凡门号为完全平方数的门在1-门号的范围内存在能整除该数的因素一定为奇数个，因为，完全平方数一定含有一个因数x，使得x*x=门号，则此时的因素为x，为一个，但是对于其他的因素一定是X*Y=门号的形式，X和Y一定不相等，存在一对，则，这样完全平方数的因素为奇数个。

 

 

 

所以，1-k号门最后的状态是，门号为完全平方数的门的状态为开，其他门为关。