Любимое занятие Луки — наблюдать за кузнечиками. Сегодня утром, прогуливаясь по парку, он обнаружил кузнечика, который прыгал по окружности длиной n метров. Лука заметил, что за один прыжок кузнечик может переместиться по часовой стрелке на k или k+1 метров от своей текущей позиции на окружности. Мальчику стало интересно, какое минимальное количество прыжков потребуется кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.
Формат входных данных
Первая строка содержит одно целое число n (1≤n≤106) — длина окружности в метрах.
Вторая строка содержит одно целое число k (1≤k≤109) — характеристика длины прыжка кузнечика в метрах.
Гарантируется, что 1≤n⋅k≤109.
Формат выходных данных
Выведите одно целое число — минимальное количество прыжков, которое придётся сделать кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.
Пояснение
Рассмотрим первый пример из условия. Один из вариантов действий кузнечика таков:
Выполнить прыжок длины 3,
Выполнить прыжок длины 4,
Выполнить прыжок длины 3.
Таким образом, суммарно кузнечик преодолеет 3+4+3=10 метров, то есть вернётся в исходную точку.
Во втором примере из условия кузнечику достаточно выполнить пять прыжков длины 2.
В третьем примере из условия можно выполнить один прыжок длины 8 и два прыжка длины 7. Таким образом, суммарно кузнечик преодолеет 8+7+7=22 метра, то есть обойдёт окружность дважды и вернётся в исходную точку.
1 Ответ
Ответ:
import sys
def get():
return sys.stdin.readline().strip()
def put(s):
sys.stdout.write(s)
def calc(a, b, n):
if a + b >= n:
return a + b — n
return a + b
def solve():
n = int(get())
k = int(get())
used = [False] * n
dist = [0] * n
step1 = k % n
step2 = (k + 1) % n
used[step1] = True
used[step2] = True
q = [0] * (10*n)
q[0] = step1
q[1] = step2
top = 0
back = 2
dist[step1] = 1
dist[step2] = 1
while not used[0]:
node = q[top]
top += 1
if not used[calc(node, step1, n)]:
used[calc(node, step1, n)] = True
dist[calc(node, step1, n)] = dist[node] + 1
q[back] = (calc(node, step1, n))
back += 1
if not used[calc(node, step2, n)]:
used[calc(node, step2, n)] = True
dist[calc(node, step2, n)] = dist[node] + 1
q[back] = (calc(node, step2, n))
back += 1
put(str(dist[0]))
solve()