Дейв уже дал конструктивный и эффективный ответ, но я хотел бы поделиться некоторыми математическими соображениями.
В течение некоторого времени я игнорирую часть + 2, так как она имеет меньшее значение, и сконцентрируюсь на общей форме этого вопроса: учитывая два положительных целых числа a и b, можно проверить, может ли быть число X представляется как k*a + m*b, где k и m - неотрицательные целые числа. Расширенный евклидов алгоритм по существу гарантирует, что:
Если число X не делится на GCD(a,b), его нельзя представить как k*a + m*b с целыми числами k и m
Если число X делится на GCD(a,b) и больше или равно a*b, его можно представить как k*a + m*b с неотрицательным целым числом k и 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, вы всегда можете получить оба коэффициента неотрицательными таким образом. (Примечание: это, очевидно, не самый эффективный способ найти подходящую пару этих коэффициентов, но, поскольку вы только спрашиваете, существуют ли такие коэффициенты, этого должно быть достаточно.)
Таким образом, единственная серая область - это числа 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 выше:
- Рассчитать коэффициенты GCD и Безу, используя расширенный евклидов алгоритм (если фиксированные
a и b зафиксированы, это можно кэшировать, но даже если это не так быстро, в любом случае).
- Проверьте условия № 1 (определенно нет) и № 2 (определенно да) из приведенного выше
- Для значения в диапазоне
(0, a*b) зафиксируйте некоторые коэффициенты, просто умножив коэффициенты Безу на X/gcd. F
- Найдите, какое из двух значений отрицательно, и найдите минимальный множитель, чтобы исправить это, обменяя один коэффициент на другой.
- Примените этот множитель к другому (изначально положительному) коэффициенту и проверьте, остается ли он положительным.
Этот алгоритм работает, потому что все возможные решения для X = k*a + m*b могут быть получены из некоторого базового решения (k0, m0), используя (k0 + n*b/gcd, m0 + n*a/gcd) для некоторого целого числа n. Таким образом, чтобы выяснить, существует ли решение с k >= 0 и m >= 0, все, что вам нужно, это найти решение с минимальным положительным значением k и проверить m для него.
Сложность этого алгоритма определяется логарифмическим алгоритмом Расширенного Евклида. Если это может быть кэшировано, все остальное просто постоянное время.