j*****q
发帖数: 33 | 1 老题目：
100个灯亮，第一次全关，第二次开2的倍数的灯，第三次关3的倍数的灯。。。。
到第一百次
多少灯亮，多少灭？
谢谢拉！ |
l******l
发帖数: 497 | 2 最后只有完全平方数（4,9,...)留着
如果不是完全平方，约数是成对出现的 |
r*******e
发帖数: 7583 | 3 对n因数分解
任何一个小于sqrt(n)的因数，必然有一个对应的大于sqrt(n)的因数
n是平方数的时候，因数个数就不成对了
【在 j*****q 的大作中提到】
: 老题目：
: 100个灯亮，第一次全关，第二次开2的倍数的灯，第三次关3的倍数的灯。。。。
: 到第一百次
: 多少灯亮，多少灭？
: 谢谢拉！
|
r*********2
发帖数: 88 | 4 1，4，9，...k^2,....是暗的
这些号的灯factor有1和他本身，这两遍一关一开抵消，状态不变
在第k遍开关k倍数的灯的时候状态会被改变
如果有其他非平方的因子，比如27=3×9，在第3遍和第9遍的时候会被分别改变状态，
互相抵消状态不变
【在 j*****q 的大作中提到】
: 老题目：
: 100个灯亮，第一次全关，第二次开2的倍数的灯，第三次关3的倍数的灯。。。。
: 到第一百次
: 多少灯亮，多少灭？
: 谢谢拉！
|
g**e
发帖数: 6127 | 5 这题是容易的，位置是完全平方数的灯是亮着的
还是joseph problem比较麻烦
【在 j*****q 的大作中提到】
: 老题目：
: 100个灯亮，第一次全关，第二次开2的倍数的灯，第三次关3的倍数的灯。。。。
: 到第一百次
: 多少灯亮，多少灭？
: 谢谢拉！
|
j*****q
发帖数: 33 | 6 什么是joseph problem啊？麻烦介绍一下：） |
g**e
发帖数: 6127 | 7 http://en.wikipedia.org/wiki/Josephus_problem
【在 j*****q 的大作中提到】
: 什么是joseph problem啊？麻烦介绍一下：）
|
f*******p
发帖数: 704 | 8 不对吧，位置为2的灯显然是亮着的啊。
【在 g**e 的大作中提到】
: 这题是容易的，位置是完全平方数的灯是亮着的
: 还是joseph problem比较麻烦
|
f*******p
发帖数: 704 | 9 4号灯不是亮的吗？
t = 0, 4号灯是亮的
t = 1,4号灯是暗的 （所有的灯都关了）
t = 2, 4号灯又亮了 （打开2的倍数的灯）
t = 3, 4号灯还是亮的 （关掉3的倍数的灯）
t = 4, 4号灯还是亮的 （打开4的倍数的灯）
t > 5的时候对4号灯没影响了
【在 r*********2 的大作中提到】
: 1，4，9，...k^2,....是暗的
: 这些号的灯factor有1和他本身，这两遍一关一开抵消，状态不变
: 在第k遍开关k倍数的灯的时候状态会被改变
: 如果有其他非平方的因子，比如27=3×9，在第3遍和第9遍的时候会被分别改变状态，
: 互相抵消状态不变
|
l*********r
发帖数: 674 | 10 t=4 应该暗
【在 f*******p 的大作中提到】
: 4号灯不是亮的吗？
: t = 0, 4号灯是亮的
: t = 1,4号灯是暗的 （所有的灯都关了）
: t = 2, 4号灯又亮了 （打开2的倍数的灯）
: t = 3, 4号灯还是亮的 （关掉3的倍数的灯）
: t = 4, 4号灯还是亮的 （打开4的倍数的灯）
: t > 5的时候对4号灯没影响了
|
|
|
g**e
发帖数: 6127 | 11 条件看反了，开始灯是亮着的。所以最后完全平方数位置的灯灭，其他的亮
【在 f*******p 的大作中提到】
: 不对吧，位置为2的灯显然是亮着的啊。
|
f*******p
发帖数: 704 | 12 那我哪里推错了呢？
第一次的时候#4是暗的，第二次开2的倍数的灯，所以#4亮了，第三次关3的倍数的灯，
因为4不是3的倍数，所以#4还是亮的，第四次开4的倍数的灯，所以#4还是亮的啊
除非。。。。
这里所谓的“开”和“关”，指的不是真正的开和关，不是说“开”就是把灯打开，“
关”就是灯暗了，而是说把那个switch拨一下
【在 l*********r 的大作中提到】
: t=4 应该暗
|
g**e
发帖数: 6127 | 13 是的，准确的描述应该是拨动开关一次
【在 f*******p 的大作中提到】
: 那我哪里推错了呢？
: 第一次的时候#4是暗的，第二次开2的倍数的灯，所以#4亮了，第三次关3的倍数的灯，
: 因为4不是3的倍数，所以#4还是亮的，第四次开4的倍数的灯，所以#4还是亮的啊
: 除非。。。。
: 这里所谓的“开”和“关”，指的不是真正的开和关，不是说“开”就是把灯打开，“
: 关”就是灯暗了，而是说把那个switch拨一下
|
C******a
发帖数: 33 | 14 +[100/2]=50
-[50/3] =-16
+[16/4] =4
- [4/5] =0 |
g******0
发帖数: 221 | 15 make a marker.
【在 j*****q 的大作中提到】
: 老题目：
: 100个灯亮，第一次全关，第二次开2的倍数的灯，第三次关3的倍数的灯。。。。
: 到第一百次
: 多少灯亮，多少灭？
: 谢谢拉！
|
