Найти номер элемента массива, который можно сформировать с помощью операции сложения / вычитания двух других чисел с третьим числом

Question

Даны три числа d, a, b и массив целых чисел. Мы можем добавлять / вычитать a или b к d любое количество раз. Мы должны найти количество чисел в массиве, которое можно сформировать, применив эти операции к d.

Пример: если массив равен [14, 15, 63] и d = 4, a = 7 и b = 9;

Тогда вывод должен быть 2. Как 14 = 4 + (9 - 7) + (9 - 7) + (9 - 7) + (9 - 7) + (9 - 7) 63 = 4 + 9 + 9 + 9 + 9 + 9 + 7 + 7 Но 15 нельзя получить с любой комбинацией. таким образом, выход составляет 2.

Пожалуйста, предложите алгоритм для расчета этого. Заранее спасибо.

Answer 1

Просто чтобы добавить немного подробностей к комментарию @ user3386109,

Даны три числа d, a, b и массив целых чисел.Мы можем добавлять / вычитать a или b к d любое количество раз.Мы должны найти число чисел в массиве, которое можно сформировать, применив эти операции к d.

Пусть элемент в массиве будет x,

Теперь, скажем, x = d + a*i + b*j, где i и j - любые целые числа.Если это нужно сохранить, тогда x - d = a*i + b*j.Давайте посмотрим, что должен сказать правый термин:

Из тождество Безу

тождество Безу - пусть a и b - целые числа с наибольшим общим делителем d.Тогда существуют целые числа x и y, такие что ax + by = d.В более общем смысле целые числа в форме ax + by - это числа, кратные d.

Мы видим, что a*i + b*j - это числа, кратные GCD(a,b).Таким образом, разница x-d должна делиться на GCD(a,b), как указывал @AshutoshTiwari.