每日一题[556]忽明忽暗

有编号为$1,2,3,\cdots ,100$的$100$盏灯和编号为$1,2,3,\cdots ,100$的$100$个操作员．$100$盏灯初始时都是关闭的，$100$个操作员顺次操作，其中编号为$k$的操作员把所有编号为$k$的倍数的灯改变状态，如编号为$3$的操作员把编号为$3,6,9,\cdots ,99$的灯中关闭的灯打开，打开的灯关闭．那么最后亮着的灯有多少盏？

---

分析与解　显然编号为$k$的灯会被编号为$k$的约数的操作员操作，因此$k$有奇数个约数时，编号为$k$的灯最后是亮着的．而考虑到将一个数$x$的约数按乘积为$x$的方式配对：对于$x$的任意一个约数$m$，$\dfrac xm$也是$x$的约数，所以$x$的约数成对出现，所以$x$有奇数个约数，当且仅当存在一对约数，满足$m=\dfrac xm$，即$x$为完全平方数．

综上所述，最后亮着的灯有$10$盏，其编号分别为

$$1,4,9,16,25,36,49,64,81,100.$$

注　也可以通过计数原理直接计算一个数的约数个数．首先将这个数进行质因数分解：

$$x=p_1^{n_1}p_2^{n_2}\cdots p_k^{n_k},$$ 其中$p_i,i=1,2,\cdots,k$是质数，$n_i\in \mathcal{N}^*$，则$x$的约数$a$具有形式 $$a=p_1^{m_1}p_2^{m_2}\cdots p_k^{m_k},$$ 其中$m_i=0,1,2,\cdots,n_i,i=1,2,\cdots,k$可以取$n_i+1$个不同的数，由分步乘法计数原理知$x$的约数个数为 $$(n_1+1)(n_2+1)\cdots(n_k+1).$$ 如$12=2^2\times 3^1$的约数个数为$(2+1)\times (1+1)=6$个．

$x$的约数个数为奇数当且仅当$n_i$均为偶数，此时$x$为完全平方数．