确定一个数字是否由其他两个数字相乘的算法

戴夫（Dave）已经给出了一个建设性的有效答案，但我想分享一些背后的数学知识。

一段时间以来，我将忽略该+ 2部分，因为它的意义不大，而将注意力集中在此问题的一般形式上：给定两个正整数，a并b检查数字是否X可以表示为k*a + m*bwherek和m是非负整数。该扩展欧几里得算法本质上保证：

1. 如果数字X不能被整除GCD(a,b)，则不能将其表示为k*a + m*b整数k和m

2. 如果numberX可被number整除GCD(a,b)并大于或等于a*b，则可以k*a + m*b用非负整数kand表示m。这源于d = GCD(a,b)可以以这种形式表示的事实（我们称它为d = k0*a + m0*b）。如果那样的X = Y*d话X = (Y*k0)*a + (Y*m0)*b。如果这两个系数中的一个为负，则可以将另一个系数进行加法或减法，a*b以换取所需的倍数X = (Y*k0 + b)*a + (Y*m0 - a)*b。并且由于X >= a*b您始终可以通过这种方式使两个系数均为非负数。（注意：这显然不是找到合适的一对系数的最有效方法，但是由于您仅询问是否存在这样的系数就足够了。）

3. 因此，唯一的灰色区域是该范围内的X可被GCD(a,b)其整除的数字(0, a*b)。我不知道有关此区域的任何一般规则，但是您可以对其进行显式检查。

因此，您可以执行＃3中所述的预计算，然后可以通过简单的比较+可能会针对范围的预计算布尔数组检查几乎立即回答此问题(0, a*b)。

如果实际的问题是关于k*a + m*b + c形式，其中a，b和c是固定的，很容易转换到k*a + m*b仅通过减去问题c的X。

更新（大值的a和b）

如果您的a和b大，因此您无法(0, a*b)事先缓存该范围，那么我唯一的想法就是通过合理有效的算法按需检查该范围内的值。代码如下：

function egcd(a0, b0) {
    let a = a0;
    let b = b0;
    let ca = [1, 0];
    let cb = [0, 1];

    while ((a !== b) && (b !== 0)) {
        let r = a % b;
        let q = (a - r) / b;
        let cr = [ca[0] - q * cb[0], ca[1] - q * cb[1]];
        a = b;
        ca = cb;
        b = r;
        cb = cr;
    }

    return {
        gcd: a,
        coef: ca
    };
}

function check(a, b, x) {
    let eg = egcd(a, b);
    let gcd = eg.gcd;
    let c0 = eg.coef;

    if (x % gcd !== 0)
        return false;

    if (x >= a * b)
        return true;

    let c1a = c0[0] * x / gcd;
    let c1b = c0[1] * x / gcd;
    if (c1a < 0) {
        let fixMul = -Math.floor(c1a / (b / gcd));
        let c1bFixed = c1b - fixMul * (a / gcd);
        return c1bFixed >= 0;
    }
    else { //c1b < 0
        let fixMul = -Math.floor(c1b / (a / gcd));
        let c1aFixed = c1a - fixMul * (b / gcd);
        return c1aFixed >= 0;
    }
}

该代码背后的思想基于上面步骤2中描述的逻辑：

1. 使用扩展的欧几里得算法计算GCD和Bézout系数（如果a和b固定，则可以将其缓存，但即使这样也不算很快）。
2. 从上面检查条件＃1（绝对不是）和＃2（绝对是）
3. 对于(0, a*b)范围内的值，只需将Bézout系数乘以即可确定一些系数X/gcd。F
4. 找出两者中的哪一个为负数，并找到最小乘数以通过将一个系数换成另一个系数来固定它。
5. 将此乘数应用于其他（最初为正）系数，并检查其是否仍为正。

该算法的工作，因为所有可能的解决方案X = k*a + m*b可以从一些基本的解决方案来获得(k0, m0)使用的(k0 + n*b/gcd, m0 + n*a/gcd)一些整数n。因此，要找出是否有与这两个解决方案k >= 0和m >= 0所有你需要的是找到与最小正解k，并检查m它。

该算法的复杂性由对数的扩展欧几里得算法决定。如果可以缓存，则其他所有内容都是固定时间。