100 Lockers: There are 100 closed lockers in a hallway. A man begins by opening all 100 lockers.Next, he closes every second locker. Then, on his third pass, he toggles every third locker (closes it if it is open or opens it if it is closed). This process continues for 100 passes, such that on each pass i, the man toggles every ith locker. After his 100th pass in the hallway, in which he toggles only locker #100, how many lockers are open?
Hints: #139, #172, #264, #306
解法
换个思路想这个问题：
- 所有锁一开始都是closed状态
- 编号X的锁会被toggle奇数次还是偶数次？如果是奇数次那么最后就是opened，偶数次那么回归closed
编号X的锁会被toggle几次取决于它有几个能够整除它的因子，这些因子 1 <= 因子 <= X。
如果X可以被a整除：b = X / a，那么a和b都是X的因子。那么是否意味着X的因子数肯定是偶数呢？
不是的，比如4的因子是：1、2、4，9的因子是：1、3、9，16的因子是1、2、4、8、16。
其实也就是说如果a == b，那么X的因子数就是奇数个。什么时候a == b？X能够被完整开根号的时候。
在1到100里，能够被正好开根号的数字有1 * 1、2 * 2、3 * 3、。。。、10 * 10，一共10个。所以最终会有10个锁会是opened状态。
评论