网站版式,wordpress会员vip插件,wordpress缩 图,网站收录低的原因有编号1~100个灯泡#xff0c;起初所有的灯都是灭的。有100个同学来按灯泡开关#xff0c;如果灯是亮的#xff0c;那么按过开关之后#xff0c;灯会灭掉。如果灯是灭的#xff0c;按过开关之后灯会亮。
现在开始按开关。
第1个同学#xff0c;把所有的灯泡开关都按一次…有编号1~100个灯泡起初所有的灯都是灭的。有100个同学来按灯泡开关如果灯是亮的那么按过开关之后灯会灭掉。如果灯是灭的按过开关之后灯会亮。
现在开始按开关。
第1个同学把所有的灯泡开关都按一次(按开关灯的编号 1,2,3,......100)。 第2个同学隔一个灯按一次(按开关灯的编号 2,4,6,......,100)。 第3个同学隔两个灯按一次(按开关灯的编号 3,6,9,......,99)。 ......
问题是在第100个同学按过之后有多少盏灯是亮着的
这个问题有一个数学上的解决方法。可以看出被按了奇数次的灯泡应该是亮着的被按了偶数次的灯泡应该是灭的。那么什么样的灯泡被按了奇数次什么样的灯泡又被按了偶数次呢从按的过程可以发现如果一个灯泡的编号具有偶数个因子那么该灯泡就被按了偶数次反之按了奇数次。现在的问题又变成什么样的编号具有奇数个因子什么样的编号具有偶数个因子这涉及到一个叫做质因数分解的定理大概的意思是说任何正数都能被唯一表示成多个质因数幂次乘积的方式。
例如:
142*7 502*5^2 ... 1002^2*5^2
也就是N(p[1]^e[1])*(p[2]^e[2])*......*(p[k]^e[k])其中p[i]是质数e[i]是p[i]的幂次。而由这个公式我们又可以导出一个数有多少个因子的计算公式:FactorNumber(N)(e[1]1)*(e[2]1)*......*(e[k]1)。
那么什么条件下满足FactorNumber(N)是奇数呢显然必须所有的e[1],e[2],......,e[k]都必须是偶数这样才能保证e[i]1是奇数结果乘积才能是奇数。而由于e[1],e[2],......,e[k]都是偶数,那么N一定是一个完全平方数(因为sqrt(N)(p[1]^(e[1]/2))*(p[2]^(e[2]/2))*......*(p[k]^(e[k]/2))是整数) 。回到按灯泡的问题上来1~100中完全平方数有1,4,9,16,25,36,49,64,81,100这10个数也就是说最后只有编号为这10个数的灯是亮着的。
参考博客http://www.cnblogs.com/haolujun/archive/2012/10/10/2719031.html
