Олимпиада информатика 10 класс

Лука наблюдает за кузнечиками

Ограничение по времени: 1

секунда

Любимое занятие Луки —
наблюдать за кузнечиками. Сегодня утром, прогуливаясь по парку, он обнаружил кузнечика, который прыгал по окружности длиной n метров. Лука заметил, что за один прыжок кузнечик может переместиться по часовой стрелке на k или k+1

метров от своей текущей позиции на окружности. Мальчику стало интересно, какое минимальное количество прыжков потребуется кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.
Формат входных данных

Первая строка содержит одно целое число n
(1≤n≤106) — длина окружности в метрах.
Вторая строка содержит одно целое число k (1≤k≤109) — характеристика длины прыжка кузнечика в метрах.
Гарантируется, что 1≤n⋅k≤109

.
Формат выходных данных

Выведите одно целое число —

минимальное количество прыжков, которое придётся сделать кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.
Система оценки

Решения, правильно работающие только для случаев, когда n
не превосходит 100, будут оцениваться в 60

баллов.
Пояснение

Рассмотрим первый пример из условия. Один из вариантов действий кузнечика таков:

Выполнить прыжок длины 3

,
Выполнить прыжок длины 4
,
Выполнить прыжок длины 3

.

Таким образом, суммарно кузнечик преодолеет 3+4+3=10
метров, то есть вернётся в исходную точку.
Во втором примере из условия кузнечику достаточно выполнить пять прыжков длины 2.
В третьем примере из условия можно выполнить один прыжок длины 8 и два прыжка длины 7. Таким образом, суммарно кузнечик преодолеет 8+7+7=22 метра, то есть обойдёт окружность дважды и вернётся в исходную точку.