n个数凑不出来的数

这个问题属于数学范畴中的“零钱问题”，也称为“凑硬币问题”或“换硬币问题”。假设有n种不同面值的硬币，它们的面值分别为c1, c2, ..., cn，现在需要用这些硬币凑出一个总价值为amount的钱数。如果无法凑出，则称这个amount为“凑不出来的数”。

根据数学原理，当且仅当“凑不出来的数”大于等于c1, c2, ..., cn中任意一个数的总和时，才可能无法凑出。因此，我们可以先对硬币面值进行升序排序，然后从小到大枚举每个面值，同时记录当前能够凑出的最大金额maxSum。如果下一个硬币面值大于maxSum+1，则maxSum+1即为“凑不出来的数”。

具体实现可以使用贪心算法，时间复杂度为O(nlogn)。这里给出Python代码实现：

def get_unreachable_num(coins, amount):
    coins.sort()
    max_sum = 0
    for coin in coins:
        if coin > max_sum + 1:
            return max_sum + 1
        max_sum += coin
    return max_sum + 1 if max_sum >= amount else -1

其中，coins是一个列表，存储n个硬币的面值；amount为需要凑出的总金额。该函数返回“凑不出来的数”，如果不存在则返回-1。

相关问题

java最少硬币问题规定硬币个数

如果要求在Java最少硬币问题中限制硬币个数，则需要对状态定义进行修改。设 f(i, j) 表示只考虑前 j 种硬币凑出金额 i 所需的最少硬币数量。则有以下的状态转移方程：

f(i, j) = min{f(i, j-1), f(i-coins[j], j) + 1}

其中，coins[j] 表示第 j 种硬币的面值。

初始状态为 f(0, j) = 0，因为凑出金额为 0 不需要任何硬币。

最终的答案为 f(amount, n)，其中 n 为硬币的种类数量。

以下是 Java 代码实现：

public int coinChange(int[] coins, int amount, int limit) {
    int n = coins.length;
    int[][] dp = new int[amount + 1][n + 1];
    for (int i = 1; i <= amount; i++) {
        Arrays.fill(dp[i], amount + 1);
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = 0;
    }
    for (int i = 1; i <= amount; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i][j - 1];
            if (coins[j - 1] <= i && dp[i - coins[j - 1]][j] < amount) {
                dp[i][j] = Math.min(dp[i][j], dp[i - coins[j - 1]][j] + 1);
            }
        }
    }
    return dp[amount][n] > limit ? -1 : dp[amount][n];
}

其中，dp[i][j] 表示只考虑前 j 种硬币凑出金额 i 所需的最少硬币数量。如果 dp[i][j] > limit，则表示无法凑出该金额，返回 -1。否则返回 dp[amount][n] 的值即可。

给定一组n个正整数，要求每次选其中一个数乘以或除以一个素数（称为一次凑数），问至少需要凑数多少次可以把所有的数都凑成相等。

这是一个非常经典的数学问题，可以用数学归纳法来解决。首先，如果只有两个数a和b，那么最少需要凑数的次数就是它们之间的差值的因子个数，因为每次凑数只能改变一个数的值，所以需要凑数的次数就等于它们之间的差值的因子个数。

接下来考虑对于n个数的情况。我们可以先对n个数求出它们的最大公约数g，然后将它们都除以g，这样它们就都凑成了一样的数，而且它们的最大公约数为1。

现在我们要将它们凑成相等的数，假设它们都等于k，那么我们需要将每个数a[i]都凑成k。我们可以把k分解质因数，得到k=p1^a1 * p2^a2 * ... * pn^an，其中p1、p2、...、pn都是不同的素数。由于每次凑数只能乘以或除以一个素数，那么对于每个素数pi，我们需要将所有的a[i]都凑成pi^x的形式，其中x是一个整数。

对于任意一个素数pi，我们可以将所有的a[i]对pi取模，得到一组余数r[1]、r[2]、...、r[n]，其中0 <= r[i] <= pi-1。如果这些余数中有一个数不为0，那么我们就必须将这个数凑成0，需要至少一次凑数。如果这些余数都为0，那么我们就不需要凑数了，因为a[i]都能被pi整除。

因此，对于每个素数pi，我们需要将所有的余数都凑成0。这样，我们可以将所有的余数分成若干组，其中每组的余数都是pi的倍数，然后对于每组余数，我们可以用相同的方法来计算需要凑数的次数。最终，所有素数的凑数次数之和就是我们要求的答案。

需要注意的是，我们需要用到一个定理，即对于任意一个正整数n，它的质因数分解中最多只有log2(n)个质因数。因此，在实际计算中，我们只需要枚举不超过log2(max(a[i]))的素数即可。