Если в массиве А есть два взаимно простых числа m и n, то для любого числа z, большего чем mn существуют такие неотрицательные x, y, что z = xm + yn. Таким образом, можно считать, что если в А есть два взаимно простых, то все числа, большие 10¹⁰ представимы таким образом. Ну а для меньших как-то перебрать по-умному надо:)

Пусть дано число C и требуется проверить можно ли его представить.

Можно устроить проверку так: выбрать любое a_i (например, a₀) и проверить, можно ли из C вычитать остальные числа так, чтобы получился 0 по модулю a₀. Понятно, что ответ зависит от остатка C при делении на a₀, при этом надо, чтобы при вычитании не получилось в конце концов отрицательного числа. Таким образом, можно посчитать такую динамику: dp[x] — какое минимальную комбинацию a_i-х можно вычесть из числа, у которого остаток x по модулю a₀, так, чтобы получился 0 по модулю a₀.

Проверка будет выглядеть так: [0  ≤  C — dp[C % a₀ ]].

Таким образом, можно для каждого остатка найти минимальное число, начиная с которого числа с таким остатком представимы.

Стресс до 10⁵: http://www.everfall.com/paste/id.php?0hnbvd2rto20