2016 AMC 10A Problem 22

The divisor-count rule. Write a number as a product of prime powers, add $1$ to each exponent, and multiply. For example $12 = 2^2 \cdot 3^1$ has $(2+1)(1+1) = 6$ divisors: $1, 2, 3, 4, 6, 12$.

1. What cubing does. Cubing $n$ multiplies every exponent by $3$. So in $n^3$ every prime has an exponent that is a multiple of $3$: $0, 3, 6, \ldots$
2. What multiplying by $110 = 2 \cdot 5 \cdot 11$ does. It adds $1$ to the exponents of $2$, $5$ and $11$. So in $110n^3$:
- each of $2$, $5$, $11$ has exponent $1, 4, 7, \ldots$ and gives a factor of $2, 5, 8, \ldots$ to the divisor count;
- any other prime in $n$ has exponent $3, 6, \ldots$ and gives a factor of $4, 7, \ldots$
3. Match with $110$. The divisor count is $110 = 2 \cdot 5 \cdot 11$, a product of just three primes. The primes $2$, $5$, $11$ always give three factors, each at least $2$, so each of those three factors must be a single prime from $2, 5, 11$, and nothing is left over. That means:
- $n$ has no primes other than $2$, $5$ and $11$;
- the three factors are $2$, $5$ and $11$ in some order.
4. Back to exponents. A factor of $2$ means exponent $1$ in $110n^3$ (exponent $0$ in $n$). A factor of $5$ means exponent $4$ (exponent $1$ in $n$). A factor of $11$ means exponent $10$ (exponent $3$ in $n$). So among $2, 5, 11$, one prime is missing from $n$, one appears once, and one appears cubed. One example is $n = 2^3 \cdot 5 = 40$. Check: $110 \cdot 40^3 = 2^{10} \cdot 5^4 \cdot 11$, with $11 \cdot 5 \cdot 2 = 110$ divisors.
5. Now $81n^4$. Raising to the 4th power multiplies the exponents by $4$: one prime to the $4$th, another to the $12$th. And $81 = 3^4$ brings in the prime $3$, which is not in $n$. So
$$81n^4 = 3^4 \cdot p^4 \cdot q^{12}$$
for two different primes $p, q$ from $2, 5, 11$. With $n = 40$ this is $3^4 \cdot 5^4 \cdot 2^{12}$.
6. The divisor count is $(4 + 1)(4 + 1)(12 + 1) = 5 \cdot 5 \cdot 13 = 325$, whichever primes $p$ and $q$ are.

The answer is $\boxed{\textbf{(D)}\ 325}$.

The number of divisors depends only on the exponents in the prime factorization. Cubing makes every exponent a multiple of $3$, and multiplying by $110$ bumps three of them by one, so the primes of $110$ behave differently from all other primes. Since $110$ has only three prime factors, there is no room for anything else. We never had to find $n$ exactly: every possible $n$ gives the same final count.

Write $n = 2^a 5^b 11^c \cdot k$ where $k$ has no factor of $2$, $5$ or $11$, and let the primes of $k$ have exponents $e_1, e_2, \dots$ in $n$. Then
$$110 n^3 = 2^{3a+1}\, 5^{3b+1}\, 11^{3c+1} \prod p_i^{3e_i},$$
so its divisor count is
$$(3a+2)(3b+2)(3c+2)\prod (3e_i + 1) = 110 = 2\cdot 5\cdot 11.$$

Each of the three factors $3a+2$, $3b+2$, $3c+2$ is at least $2$, so their product is at least $8$; the leftover $\prod(3e_i+1)$ must then be a divisor of $110$ that is at most $13$ and is $1$ more than a multiple of $3$. The candidates $1, 10$ fail unless the product is $1$ (with $10$ the remaining product would be $11$, too small to be a product of three numbers each at least $2$). So $k = 1$ and $\{3a+2, 3b+2, 3c+2\} = \{2, 5, 11\}$, i.e. $\{a, b, c\} = \{0, 1, 3\}$ in some order.

Thus $n = p\, q^3$ for two distinct primes $p, q \in \{2, 5, 11\}$, and neither is $3$. Then
$$81 n^4 = 3^4\, p^4\, q^{12},$$
which has $(4+1)(4+1)(12+1) = 5\cdot 5\cdot 13 = 325$ divisors, regardless of which primes play the roles of $p$ and $q$.

The answer is $\boxed{\textbf{(D)}\ 325}$.