要解决这个问题，我们需要判断大整数k能否表示为给定质数数组中元素的非负整数系数线性组合（即存在非负整数a₁,a₂,...,aₙ使得k = a₁p₁ + a₂p₂ + ... + aₙpₙ）。由于数组元素都是质数，它们的GCD恒为1，但这并不意味着所有正整数都能被表示（比如[5,7,13]中16无法表示），因此我们需要结合数论性质与高效算法来实现。

核心思路：模最小质数的剩余类预处理 #

这个问题本质是广义硬币找零问题的判断变种。对于超大整数k，常规动态规划（逐个计算到k）会因内存和时间限制无法实现，因此我们采用剩余类优化：
假设数组中最小的质数为m，那么所有能表示的数可以按模m的余数分为m类。对于每个余数r（0 ≤ r < m），我们只需要找到该类中最小的可表示数，那么所有大于等于这个数且与r同余的数都能被表示（因为加上若干个m即可）。

具体实现步骤 #

1. 预处理数组：去重、排序，提取最小质数m，同时将所有数转换为BigInt以支持大整数运算。
2. 边界情况处理：快速排除无需复杂计算的场景（如k=0、k < 最小质数、k本身是数组中的质数）。
3. 计算每个余数类的最小可表示数：用BFS算法，从0出发遍历所有质数的组合，记录每个余数对应的最小可表示数。
4. 判断大整数k：计算k mod m得到余数r，若k大于等于r类的最小可表示数且同余，则返回true，否则返回false。

JavaScript代码实现（支持大整数） #

function isLinearCombination(k, primes) {
    // 预处理：转BigInt、去重、排序
    const primesBig = [...new Set(primes.map(p => BigInt(p)))].sort((a, b) => a < b ? -1 : 1);
    if (primesBig.length === 0) return false;

    const minPrime = primesBig[0];
    const target = BigInt(k);

    // 边界情况处理
    if (target === 0n) return true; // 全0系数的特殊情况
    if (target < minPrime) return false; // 正整数k小于最小质数，无法用非负系数组合得到
    if (primesBig.includes(target)) return true; // k本身是数组中的质数，直接返回true

    // 初始化余数数组：存储每个余数对应的最小可表示数，初始为Infinity
    const remainderCount = Number(minPrime);
    const minForRemainder = new Array(remainderCount).fill(Infinity);
    minForRemainder[0] = 0n; // 0可以被表示，对应余数0

    // 用BFS遍历所有可能的组合，更新余数类的最小可表示数
    const queue = [0n];
    const visited = new Set();
    visited.add(0n);

    while (queue.length > 0) {
        const current = queue.shift();
        for (const p of primesBig) {
            const next = current + p;
            const remainder = Number(next % minPrime);

            // 如果当前组合得到的数是该余数类的更小值，更新并加入队列
            if (next < minForRemainder[remainder]) {
                minForRemainder[remainder] = next;
                if (!visited.has(next)) {
                    visited.add(next);
                    queue.push(next);
                }
            }
        }
    }

    // 检查目标数对应的余数类是否有可表示数，且目标数足够大
    const targetRemainder = Number(target % minPrime);
    if (minForRemainder[targetRemainder] === Infinity) {
        return false; // 该余数类无任何可表示数
    }
    return target >= minForRemainder[targetRemainder];
}

// 测试用例
console.log(isLinearCombination(12, [5,7,13])); // 输出: true (5+7)
console.log(isLinearCombination(16, [5,7,13])); // 输出: false
console.log(isLinearCombination(26, [5,7,13])); // 输出: true (13*2)
console.log(isLinearCombination(1000000000000000000n, [5,7,13])); // 输出: true (1000000000000000000是5的倍数)

关键说明 #

1. 大整数支持：所有运算使用BigInt，避免了JavaScript Number的精度限制（最大精确整数为2^53-1），可以处理任意大的k。
2. 高效性：预处理阶段的时间复杂度为O(m*n)（m是最小质数，n是数组长度），由于m是质数且数组去重后规模有限，预处理速度极快；后续判断任意k仅需O(1)时间。
3. 正确性：基于数论中剩余类的性质，一旦找到余数类的最小可表示数，所有更大的同余数都能通过添加最小质数得到，完全覆盖了大整数场景。

备注：内容来源于stack exchange，提问作者Lawton