MENU

开关灯问题(数论 / 质因数分解)

2019 年 03 月 04 日 • 阅读: 3818 • 数论阅读设置

开关灯问题(质因数分解)

题目描述:

有编号1~n个灯泡,起初所有的灯都是灭的。有n个同学来按灯泡开关,如果灯是亮的,那么按过开关之后,灯会灭掉。如果灯是灭的,按过开关之后灯会亮。

现在开始按开关。

第1个同学,把所有的灯泡开关都按一次(按开关灯的编号: 1,2,3,......)。
第2个同学,隔一个灯按一次(按开关灯的编号: 2,4,6,......)。
第3个同学,隔两个灯按一次(按开关灯的编号: 3,6,9,......)。
......

问题是,在第n个同学按过之后,有多少盏灯是亮着的?

输入描述:

输入一组数据:n

输出描述:

输出开着的灯编号

样例输入:

10

样例输出:

1 2 4 9

题意

中文题面,没啥好说的。

题解

  • 首先可以想到的一个办法是直接模拟,可以用一个数组来表示开关的状态(0灭1开),然后一层循环遍历表示开关灯泡的次数,一层循环来对灯泡进行操作,时间复杂度$O(n^2)$
  • 这题还有有趣的数学解法,来自haolujun
这个问题有一个数学上的解决方法。可以看出,被按了奇数次的灯泡应该是亮着的,被按了偶数次的灯泡应该是灭的。那么什么样的灯泡被按了奇数次?什么样的灯泡又被按了偶数次呢?从按的过程可以发现,如果一个灯泡的编号具有偶数个因子,那么该灯泡就被按了偶数次,反之按了奇数次。现在的问题又变成,什么样的编号具有奇数个因子,什么样的编号具有偶数个因子?这涉及到一个叫做质因数分解的定理,大概的意思是说,任何正数都能被唯一表示成多个质因数幂次乘积的方式。

例如:

14=2*7
50=2*5^2
...
100=2^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个数的灯是亮着的。

别的没什么好说的,我就说一下为啥FactorNumber(N)=(e[1]+1)*(e[2]+1)*......*(e[k]+1),比如$50 = 2^1 * 5^2$,然后对于2我们可以选或者不选两种,对于5可以不选或者选一个或者选两个三种,所以FactorNumber(25) = (1+1)*(2+1),实际上就是组合公式,都不选就是1。

代码

代码就免了吧,可以预处理一下得到某个范围内的完全平方数,然后就直接根据n得结果了。


The end.
2019年3月4日 星期一
最后编辑于: 2019 年 03 月 07 日