联想面试时的一道智力题有100盏灯,从1~100编上号,开始时所有的灯都是关着的,第一次,把所有编号是1的倍数的灯的开关状态改变一次；第二次,把所有编号是2的倍数的灯的开关状态改变一次；

Question

联想面试时的一道智力题
有100盏灯,从1~100编上号,开始时所有的灯都是关着的,第一次,把所有编号是1的倍数的灯的开关状态改变一次；第二次,把所有编号是2的倍数的灯的开关状态改变一次；第三次,把所有编号是3的倍数的灯的开关状态改变一次；以此类推,直到把所有编号是100得倍数的灯的开关状态改变一次.问,此时所有开着的灯的编号.

Answer 1

亮的是1、4、9、16、25、36、49、64、81、100这10盏编号是完全平方数的灯,
因为它们的开关被拉的次数是奇数次.
为什么完全平方数的约数个数是奇数呢?有一个算约数个数的方法：
设某数为A,将A分解质因数是A=a1^n1*a2^n2*a3^n3……an^nn
则它的约数个数是(n1+1)*(n2+1)*(n3+1)……(nn+1)
若它是完全平方数,则n1、n2、n3……nn必须是偶数,那么(n1+1)、
(n2+1)、(n3+1)……(nn+1)都是奇数,若干个奇数相乘仍得奇数.