[数论] 来自群的一道数论计数题

据说是苹果的题，不知是不是真的，反正群里的截图就是这样的：

(46.35 KB)

2012-6-20 20:11

这个题表达得不太好，容易被误解操作，如果不是那句“即排在偶数的灯泡都被关掉”的话，估计我也会理解成每次都把第一个灯开或关。还有一点容易理解错的就是最后说的“第100轮的时候”，这个“时候”到底是指这第100轮操作了没有的呢？

那么这里我重新把题目表达一遍先。
100个灯泡排成一排，依次编号为1~100，原本都是处于关的状态。（其实是不是排成一排没关系，编号位置也没关系）
接下来对这些灯泡进行100轮的操作：第1轮将所有灯泡打开；第2轮将偶数号的灯泡都被关掉；由第3轮开始，第 $k$ 轮对被 $k$ 整除的编号的灯泡进行操作，操作的每个动作是将开着的灯泡关掉，将关掉的灯泡打开。问最终还有哪些灯泡是亮着的？

在群里我发的解答有点简略，这里我也把过程写得好一些。


对于 $n$ 号灯来说，显然最终是开或关就取决于 $n$ 的正约数个数，奇数个则开，偶数个则关。
今设 $n$ 的标准分解式是
\[n=2^{a_1}\cdot 3^{a_2}\cdot 5^{a_3}\cdot 7^{a_4}\cdots ,\]
其中各底数均是质数，各 $a_i$ 是非负整数。
由正约数个数公式
\[d(n)=(1+a_1)(1+a_2)(1+a_3)(1+a_4)\cdots\]
知，要灯泡最终是开的，即是要 $d(n)$ 为奇数，则显然所有的 $a_i$ 都要是偶数，反之亦然。而当所有的 $a_i$ 都要是偶数时显然 $n$ 是完全平方数，因此，有且只有完全平方数号的灯泡最终会开着。
因此，最终亮着的灯的编号是 1, 4, 9, 16, 25, 36, 49, 64, 81, 100，共10个。

嗯，其实也没有详细到哪去，那个正约数个数公式由乘法原理显然可得，这里就不解释太多了。

唉，数论没学过，苹果考的也太深了点吧。

哦，你一说乘法原理，就明白那个约数公式了。

嗯，不知我现在这样重新对原题目的表述有没有歧义？

先吃饭了

楼上上在群里谈及编程验证此题，可惜C++我不懂，倒是用 Mathematica 编得出来，贴了在
http://kkkkuingggg.5d6d.net/thread-539-1-1.html
g[n_, d_] := If[Mod[n, d] == 0, -1, 1];
lst = Table[-k, {k, 1, 100}];
Do[lst = lst*Table[g[k, n], {k, 1, 100}], {n, 1, 100}]
lst
得到结果
{1, -2, -3, 4, -5, -6, -7, -8, 9, -10, -11, -12, -13, -14, -15, 16,
-17, -18, -19, -20, -21, -22, -23, -24, 25, -26, -27, -28, -29, -30,
-31, -32, -33, -34, -35, 36, -37, -38, -39, -40, -41, -42, -43, -44,
-45, -46, -47, -48, 49, -50, -51, -52, -53, -54, -55, -56, -57, -58,
-59, -60, -61, -62, -63, 64, -65, -66, -67, -68, -69, -70, -71, -72,
-73, -74, -75, -76, -77, -78, -79, -80, 81, -82, -83, -84, -85, -86,
-87, -88, -89, -90, -91, -92, -93, -94, -95, -96, -97, -98, -99, 100}
可以看出只有完全平方数前面是正的，所以结果符合上面的答案。
链接内后面还有各步状态的数据，由于太长，就不贴过来了。

[i=s] 本帖最后由 都市侠影 于 2012-6-21 10:30 编辑 [/i]

我是用C写的，这么小的问题不敢劳烦C++的大驾。检查了下程序，就一个字符打错了，
把19行的a[j]*=-1打成了a[i]*=-1，一字之差啊，修改之后结果是10.

(31.03 KB)

2012-6-21 09:24

运行结果

(12.01 KB)

2012-6-21 09:24

oh，C和C++我都不懂，呵呵。

PS。论坛贴里出现 [i] 会变成斜体代码……禁用discuz代码才会正常显示

Oh