Take it like this:

There must be a 1-coin. Suppose you took k 1-coins, then you can't make k + 1 in any way other than by one k + 1-coin. Now, you have ways to make all values up to 2k + 1. Suppose you took l k + 1-coins. Then you can make all values up to l(k + 1) + k, each exactly once. Again, you need a coin with cost l(k + 1) + k + 1 = (l + 1)(k + 1) to achieve the next value. That looks suspicious: in fact, if you have x_i coins of the i-th type, the next coin must have value .

That means if we sorted the coin types that we take at least 1 coin into a sequence of x_i, then x_i - 1 divides x_i and there must be coins of type i - 1; the number of coins of the last type can be chosen easily based on the fact that if it's k, then we can make all values up to kx_n - 1.

And now that we know how many coins to use, we can do a DP on the total number of coins used for types starting with the i-th, in O(N²). I leave that up to you.

TopCoder SRM 195 Div 2, Level Three, ChangePurse, Advanced Math. (written for bare purpose of web crawlers to index the page and associate it with related query. wish it was done by tags and headers)