Фонтаны с «сбитым» таймером

В школьном дворе поставили два фонтана с таймерами.

• Фонтан A включается ровно в моменты времени 0, m, 2m, 3m, ... минут от начала отсчёта.
• Фонтан B должен был включаться в 0, p, 2p, ... минут, но мастер случайно сдвинул таймер так, что первое включение будет через 1 минуту, а дальше каждые p минут: 1, 1+p, 1+2p, ...

Найди самый ранний момент времени (в минутах от начала отсчёта), когда оба фонтана включатся одновременно. Если такого момента не бывает — выведи -1.

Важно: ответ может быть больше, чем помещается в 32-битный тип (как на олимпиадах), то есть может понадобиться 64-битная арифметика.

Формат ввода

В одной строке записаны два целых числа m и p.

Формат вывода

Выведи одно целое число — минимальное t >= 0, такое что:

• t кратно m,
• t даёт остаток 1 при делении на p.

Если такого t не существует, выведи -1.

Ограничения

• 1 <= m <= 10^9
• 2 <= p <= 10^9
• лимит времени: 1 секунда
• лимит памяти: 256 МБ

Пример

Ввод:

4 7

Вывод:

8

Пояснение: фонтан A включается в 0,4,8,12,... а фонтан B — в 1,8,15,... Первый общий момент — 8.

Ключевое наблюдение: общий момент t должен одновременно быть кратен m и давать остаток 1 по модулю p. Если t кратен m, то t = m*k для некоторого целого k. Подставляем во второе условие:

t = m*k и t % p = 1 => m*k ≡ 1 (mod p).

Это линейное сравнение. Оно имеет решение тогда и только тогда, когда gcd(m, p) делит 1, то есть когда gcd(m, p) = 1. В этом случае у числа m есть обратный элемент по модулю p.

Почему работает расширенный Евклид: он находит такие x и y, что x*m + y*p = gcd(m,p). Если gcd = 1, получаем x*m + y*p = 1, значит x*m ≡ 1 (mod p), то есть x — это и есть обратный к m по модулю p.

План решения:

• Посчитай g = gcd(m, p). Если g != 1, выведи -1.
• Запусти расширенный Евклид для (m, p), получи коэффициент x из x*m + y*p = 1.
• Приведи x к остатку: k = x % p (минимальный k >= 0).
• Ответ: t = m * k.

Сложность: O(log(min(m,p))) по времени, памяти почти не нужно.

Частая грабля: забыть проверку gcd(m,p)=1 и пытаться «найти обратный» всегда — тогда на некоторых тестах решения не существует. Также не перепутай: нужен обратный для m по модулю p, а не наоборот.