# Complexity of an algorithm to solve linear diophantine equations

A friend of mine ask me yesterday a problem, however, the interesting part for me it is not his problem, but what I will ask here.

I want to know the optimal complexity of an algorithm (I mean the complexity of the more efficient algorithm) that solves the following problem:

Input: $n\in \mathbb N, h\in \mathbb N, (a_1,\ldots,a_n)\in \mathbb N^n.$

Output: Cardinality of the set $\{(j_1,\ldots,j_n)\in \mathbb N^n:\sum_{i=1}^n j_i a_i=h\}.$

Hope the question does make sense.

• My guess is that depends on some kind of variance of the $(a_1,\ldots,a_n).$ For example, if all of them are equal the problem is trivial and it s getting more complicated when we start changing one then two etc... – user39115 Oct 1 '14 at 15:32
• If $h$ is given in binary, the result may be exponentially large, hence you cannot do better than exponential time. If $h$ is given in unary, you can easily compute the result in polynomial time using the recurrence $S_{h,a_1,\dots,a_{n+1}}=\sum_{j\le h/a_{n+1}}S_{h-ja_{n+1},a_1,\dots,a_n}$. – Emil Jeřábek Oct 1 '14 at 15:53
• Yes, yes, it is polynomial, but, I think there is maybe an explicit formula? – user39115 Oct 1 '14 at 17:19