一列正整数 $a_1,a_2,\cdots,a_n,\cdots$ 满足每个数都能整除之后的数，即 $a_n\mid a_{n+1}$，则它们模 $30$ 的余数最多可能有多少种不同的取值？
【难度】
【出处】
无
【标注】
【答案】
$21$
【解析】
将集合 $\{1,2,\cdots,30\}$ 划分为元素质因数分解后不包含 $2,3,5$ 的组成集合 $A_0$；包含 $2$ 但不包含 $3,5$ 的组成集合 $A_2$；包含 $3$ 但不包含 $2,5$ 的组成集合 $A_3$；包含 $5$ 但不包含 $2,3$ 的组成集合 $A_5$；包含 $2,3$ 但不包含 $5$ 的组成集合 $A_{2,3}$；包含 $3,5$ 但不包含 $2$ 的组成集合 $A_{3,5}$；包含 $2,5$ 但不包含 $3$ 的组成集合 $A_{2,5}$；包含 $2,3,5$ 的组成集合 $A_{2,3,5}$，如下表．\[\begin{matrix}
name &type & set & card \\ \hline
A_0&x & 1,7,11,13,17,19,23,29 & 8 \\
A_2&2^k\cdot x & 2,4,8,14,16,22,26,28 & 8\\
A_3&3^k\cdot x & 3,9,21,27 & 4\\
A_5&5^k\cdot x & 5,25 & 2\\
A_{2,3}&2^{k_1}\cdot 3^{k_2}\cdot x & 6,12,18,24 &4\\
A_{3,5}&3^{k_1}\cdot 5^{k_2}\cdot x & 15 & 1\\
A_{2,5}&2^{k_1}\cdot 5^{k_2}\cdot x & 10,20 & 2\\
A_{2,3,5}&2\cdot 3\cdot 5 & 30 & 1\\ \hline
\end{matrix}\]容易知道，如果余数数列出现了 $A_2$ 中的数，就不可能再出现 $A_0$ 中的数；类似的，如果余数数列中出现了 $A_{2,3}$ 中的数，就不可能出现 $A_2,A_3$ 中的数．因此最多取值数为\[{\rm Card}(A_0)+{\rm Card}(A_2)+{\rm Card}(A_{2,3})+{\rm Card}(A_{2,3,5})=8+8+4+1=21.\]具体的构造可行性可以利用裴蜀定理证明．
name &type & set & card \\ \hline
A_0&x & 1,7,11,13,17,19,23,29 & 8 \\
A_2&2^k\cdot x & 2,4,8,14,16,22,26,28 & 8\\
A_3&3^k\cdot x & 3,9,21,27 & 4\\
A_5&5^k\cdot x & 5,25 & 2\\
A_{2,3}&2^{k_1}\cdot 3^{k_2}\cdot x & 6,12,18,24 &4\\
A_{3,5}&3^{k_1}\cdot 5^{k_2}\cdot x & 15 & 1\\
A_{2,5}&2^{k_1}\cdot 5^{k_2}\cdot x & 10,20 & 2\\
A_{2,3,5}&2\cdot 3\cdot 5 & 30 & 1\\ \hline
\end{matrix}\]容易知道，如果余数数列出现了 $A_2$ 中的数，就不可能再出现 $A_0$ 中的数；类似的，如果余数数列中出现了 $A_{2,3}$ 中的数，就不可能出现 $A_2,A_3$ 中的数．因此最多取值数为\[{\rm Card}(A_0)+{\rm Card}(A_2)+{\rm Card}(A_{2,3})+{\rm Card}(A_{2,3,5})=8+8+4+1=21.\]具体的构造可行性可以利用裴蜀定理证明．
答案
解析
备注
