AMC10 2020 B

AMC10 2020 B · Q25

AMC10 2020 B · Q25. It mainly tests Recursion & DP style counting (basic), Primes & prime factorization.

Let $D(n)$ denote the number of ways of writing the positive integer $n$ as a product $n = f_1 \cdot f_2 \cdots f_k$, where $k \ge 1$, the $f_i$ are integers strictly greater than $1$, and the order in which the factors are listed matters (that is, two representations that differ only in the order of the factors are counted as distinct). For example, the number $6$ can be written as $6$, $2 \cdot 3$, and $3 \cdot 2$, so $D(6) = 3$. What is $D(96)$?

设 $D(n)$ 表示将正整数 $n$ 表示为 $n = f_1 \cdot f_2 \cdots f_k$ 的方法数，其中 $k \ge 1$，$f_i$ 均为严格大于 $1$ 的整数，且因子列出的顺序重要（即仅因子顺序不同的两种表示被视为不同）。例如，$6$ 可以写成 $6$、$2 \cdot 3$ 和 $3 \cdot 2$，故 $D(6) = 3$。求 $D(96)$。

(A) 112 112

(B) 128 128

(D) 172 172

(E) 184 184

Answer

Correct choice: (A)

正确答案：（A）

Solution

Answer (A): Clearly $D(1)=0$. Suppose $n>1$. The first factor $f_1$ in a representation is a divisor of $n$ with $f_1>1$. If $f_1=n$, then there is a representation with just one factor. Suppose that $f_1$ is a divisor of $n$ and $1<f_1<n$. Then the further factors after $f_1$ are exactly the representations of $\frac{n}{f_1}$. This gives a recurrence relation: If $n>1$, then \[ D(n)=1+\sum_{\substack{f\mid n\\1<f<n}} D\!\left(\frac{n}{f}\right). \] Thus a table of values of $D(2^j3^k)$ can be constructed for $j=0,1,\ldots,5$, $k=0,1$. \[ \begin{array}{c|cc} j\backslash k & 0 & 1\\ \hline 0 & 0 & 1\\ 1 & 1 & 3\\ 2 & 2 & 8\\ 3 & 4 & 20\\ 4 & 8 & 48\\ 5 & 16 & 112 \end{array} \] From the table, it can be seen that $D(96)=112$.

答案（A）：显然 $D(1)=0$。设 $n>1$。一个表示中的第一个因子 $f_1$ 是 $n$ 的一个因子且满足 $f_1>1$。若 $f_1=n$，则存在只含一个因子的表示。再设 $f_1$ 是 $n$ 的因子且 $1<f_1<n$。则在 $f_1$ 之后的其余因子，恰好对应于 $\frac{n}{f_1}$ 的所有表示。由此得到递推关系：若 $n>1$，则 \[ D(n)=1+\sum_{\substack{f\mid n\\1<f<n}} D\!\left(\frac{n}{f}\right). \] 因此可以构造 $D(2^j3^k)$ 的数值表，其中 $j=0,1,\ldots,5$，$k=0,1$。 \[ \begin{array}{c|cc} j\backslash k & 0 & 1\\ \hline 0 & 0 & 1\\ 1 & 1 & 3\\ 2 & 2 & 8\\ 3 & 4 & 20\\ 4 & 8 & 48\\ 5 & 16 & 112 \end{array} \] 由表可见 $D(96)=112$。

Topics