410523: GYM104034 3 Лука наблюдает за кузнечиками
Description
Любимое занятие Луки — наблюдать за кузнечиками. Сегодня утром, прогуливаясь по парку, он обнаружил кузнечика, который прыгал по окружности длиной $$$n$$$ метров.
Лука заметил, что за один прыжок кузнечик может переместиться по часовой стрелке на $$$k$$$ или $$$k + 1$$$ метров от своей текущей позиции на окружности. Мальчику стало интересно, какое минимальное количество прыжков потребуется кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.
Входные данныеПервая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — длина окружности в метрах.
Вторая строка содержит одно целое число $$$k$$$ ($$$1 \le k \le 10^9$$$) — характеристика длины прыжка кузнечика в метрах.
Гарантируется, что $$$1 \le n \cdot k \le 10^9$$$.
Выходные данныеВыведите одно целое число — минимальное количество прыжков, которое придется сделать кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.
Система оценкиРешения, правильно работающие только для случаев, когда $$$n$$$ не превосходит $$$100$$$, будут оцениваться в $$$60$$$ баллов.
ПримерыВходные данные10 3Выходные данные
3Входные данные
10 1Выходные данные
5Входные данные
11 7Выходные данные
3Примечание
Рассмотрим первый пример из условия. Один из вариантов действий кузнечика таков:
- Выполнить прыжок длины $$$3$$$,
- Выполнить прыжок длины $$$4$$$,
- Выполнить прыжок длины $$$3$$$.
Таким образом, суммарно кузнечик преодолеет $$$3 + 4 + 3 = 10$$$ метров, то есть вернется в исходную точку.
Во втором примере из условия кузнечику достаточно выполнить пять прыжков длины $$$2$$$.
В третьем примере из условия можно выполнить один прыжок длины $$$8$$$ и два прыжка длины $$$7$$$. Таким образом, суммарно кузнечик преодолеет $$$8 + 7 + 7 = 22$$$ метра, то есть обойдет окружность дважды и вернется в исходную точку.