Ctrl K

N-е кратное одного из двух

Сложная
Даны два делителя first и second. Выпишем по возрастанию все положительные целые числа, которые делятся хотя бы на один из них (число, делящееся на оба, выписывается один раз). Верните число, стоящее в этом списке на месте rank (нумерация с единицы). Ответ может быть очень большим, поэтому верните его остаток от деления на 10⁹ + 7. Перебирать числа по одному слишком долго: rank достигает миллиарда.
Пример 1
rank=5, first=4, second=6 → 16

Подходящие числа по возрастанию: 4, 6, 8, 12, 16, … Пятое из них — 16. Число 12 делится на оба, но считается один раз.

Пример 2
rank=3, first=5, second=5 → 15

Оба делителя равны, поэтому это просто кратные пяти: 5, 10, 15.

Пример 3
rank=1000000000, first=2, second=2 → 999999993
Ограничения
  • 1 ≤ rank ≤ 10⁹
  • 2 ≤ first, second ≤ 4 · 10⁴
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОснование из одних единиц Сложнаяk-е число таблицы умножения СложнаяФакториалы с k нулями на конце СложнаяИспытания прототипов на падение СложнаяЧисла с рабочих клавиш Сложная
загружаем Python…
Вход
rank=5, first=4, second=6
Ожидается
16

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