[NOIP2018 提高组] 货币系统属于完全背包问题：求解最大无关向量组的数量。

[NOIP2018 提高组] 货币系统

题目背景概述

NOIP2018 提高组 第一天第二题

题目描述

在网友所处的国度中，存在 n 种不同面值的货币，其中第 i 种货币的面值为 a[i]，可以假定每种货币的数量是无限的。为了便于描述，我们将具有 n 种货币、面值数组为 a[1..n] 的货币体系称为 (n,a)。

在一个健全的货币体系中，每一个非负整数金额 x 都应当能够被表示出来，也就是说，对于每一个非负整数 x，都应存在一组 n 个非负整数 t[i] 使得这些数值与对应面值相乘后的总和等于 x。然而，在网友所在的国度中，其货币体系可能并不完善，因此可能存在某些金额无法被该系统表示的情况。例如，在一个由 n=3、面值数组为 a=[2,5,9] 构成的货币系统中，金额为 1 和 3 的数值就无法被表示。

若两个货币系统 (n,a) 与 (m,b) 被认为是等价的，则当且仅当对于任意一个非负整数 x 来说，要么这两个系统都能将其表示出来，要么都无法将其表示。

如今网友们希望对现有的货币系统进行简化。他们期望找到一个新的货币系统 (m,b)，该系统与原系统 (n,a) 等价，并且其包含的货币种类数量尽可能少。他们希望你能协助完成这一任务：确定满足条件的最小可能