题目0319:灯泡开关

题目描述

初始时有n个灯泡关闭。第1轮,你打开所有的灯泡。第2轮,每两个灯泡你关闭一次。第3轮,每三个灯泡切换一次开关(如果关闭则开启,如果开启则关闭)。第i轮,每i个灯泡切换一次开关。对于第n轮,你只切换最后一个灯泡的开关。找出n轮后有多少个亮着的灯泡。

示例:

输入: 3
输出: 1 
解释: 
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 
你应该返回 1，因为只有一个灯泡还亮着。

显而易见,题目就是让统计整数i的因子个数为奇数的i的个数。由于因子个数函数 $d(x)$ 是积性函数，

$d(x) = (1 + \alpha_{1})(1+ \alpha_{2})\cdots (1 + \alpha_{k})$

其中 $x$ 的素性分解为: $x = p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}$ 。

由于 $d(x)$ 为奇数,所以 $1+\alpha_{i}$ 是奇数,亦即 $\alpha_i$ 是偶数。所以 $x$ 是完全平方数。题目即转化为统计[1 , n]中完全平方数的个数。所以答案就是 $\big\lfloor \sqrt{n} \big\rfloor$

其实 $O(n)$ 或者 $O(\sqrt{n})$ O的枚举还是能过去的:

for(int i = 1;i * i <= n;++i)   ++ans;

下面证明因子个数函数 $d(x)$ 是积性函数。虽然这样的过程到处都有

积性函数

对于任意正整数m,n互素,有F(mn) = F(m)F(n),f(x)的和函数

$F(x) = \sum_{d | x}{f(x)}$

我们先给出一个引理，然后通过引理证明。积性函数的和函数为积性函数

设积性函数f(x),其和函数为F(x)。我们需要证明的是,若(m,n) = 1,那么F(mn) = F(m)F(n)。

右边为

$\begin{aligned} F(m)F(n) &= \sum_{p | m}\sum_{q | n}f(p)f(q) \\ &= \sum_{d | mn}f(pq) \\ &= F(mn) \end{aligned}$

证毕。

而f(x) = 1肯定是积性的,(怎么乘都是1),所以 $d(x) = \sum_{d | x}{1}$ ,也是积性的。这样我们就说明了因子个数函数是积性的。

另一方面,若p是质数,则d(p) = 2。因为质数的因子只有1和它本身两个。 $d(p^{k})$ 是多少?它的因子只有 $1,p,p^{2},...,p^{k}$ 共k + 1个。那么 $d(x)$ 也就不难求得。

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(sqrt(n))