P5228 [AHOI2013] Finding Coins

Little Snake is the minister of the finance department. Recently, she decided to create a series of new currencies. Suppose the denominations she will create are $x_1, x_2, x_3 \dots$. Then $x_1$ must be $1$, and $x_b$ must be a positive integer multiple of $x_a$ ($b > a$). For example, $1, 5, 125, 250$ is a valid coin sequence, while $1, 5, 100, 125$ is not. Starting from some day, the lovely Snake fell in love with a cute thing—“rabbit dolls” (tu zi)! From then on, she took the one-way path of buying any rabbit doll she encountered. One day, she saw $N$ cute rabbit dolls. Suppose the prices of these $N$ rabbit dolls are $a_1, a_2 \dots a_N$. Now she wants to know: under which valid coin sequence, the total number of coins needed to buy these $N$ rabbit dolls is the smallest. No change can be given when buying rabbit dolls.

The first line contains an integer $N$, representing the number of rabbit dolls. The second line contains $N$ integers separated by spaces, representing the prices of the $N$ rabbit dolls.

One line containing an integer, representing the minimum number of coins paid.

$1 \leq N \leq 50$. $1 \leq a_i \leq 10^5$. Translated by ChatGPT 5