Ctrl K

Число без нулей с кратным произведением цифр

Сложная
Дано очень длинное положительное число в виде строки start и целое divisor. Назовём число **беснулевым**, если в его записи нет ни одной цифры 0. Найдите наименьшее беснулевое число, которое не меньше start и у которого произведение цифр делится на divisor. Верните его как строку. Если такого числа не существует, верните "-1".
Пример 1
start="1500", divisor=36 → '1549'

Для числа вида 15xy нужно, чтобы 5·x·y делилось на 36, то есть x·y делилось на 36; наименьший такой хвост — 49. Ответ 1549: 1·5·4·9 = 180 = 36 · 5.

Пример 2
start="2357", divisor=10 → '2357'

2·3·5·7 = 210 уже делится на 10, нулей нет — ответ само число.

Пример 3
start="99", divisor=22 → '-1'

22 = 2 · 11, а множитель 11 не даёт ни одна цифра — ответ "-1".

Ограничения
  • 2 ≤ len(start) ≤ 2 · 10⁵
  • start состоит из цифр и не начинается с 0
  • 1 ≤ divisor ≤ 10¹⁴
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиНаибольший палиндром, кратный числу СложнаяЗнаки между цифрами СложнаяБуквенный ребус на сложение СложнаяУзор, вплетённый несколько раз СложнаяСамые весомые выборки разных букв Сложная
загружаем Python…
Вход
start="1500", divisor=36
Ожидается
'1549'

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 96 тестов на сервере, включая скрытые.