Маша и Паша живут на одной улице, и их дома разделены только парком, в котором друзья любят гулять. В центре парка есть красивый фонтан, у которого Маша и Паша хотят сегодня…

Ниже приводится подробное решение с кратким объяснением и готовым кодом на Python.

Идея решения

• Время прибытия каждой из них к фонтану чередуется: Маша посещает фонтан на временах m, 3m, 5m, ...; Паша — на p, 3p, 5p, ...
• Встреча у фонтана возможна только тогда, когда оба окажутся у фонтана в одно и то же время: t = m(2k+1) = p(2l+1).
• Пусть g = gcd(m, p). Запишем m = gm1, p = gp1, где gcd(m1, p1) = 1. Уравнение становится m1(2k+1) = p1(2l+1). Так как m1 и p1 взаимно просты, чтобы левая и правая части были равны, обе множители m1 и p1 должны быть нечетными. Следовательно, чтобы встреча была возможна, должны выполняться условия:
  • m/g и p/g оба нечетные (то есть v2(m) = v2(p)).
• Если условие выполняется, минимальное время встречи равно НОК(m, p) = m * p / gcd(m, p).
• Если условие не выполняется, встреча невозможна.

Пример: m = 3, p = 5 → gcd = 1, m/g = 3, p/g = 5 оба нечетные → встреча через t = lcm(3,5) = 15 минут. Пример: m = 2, p = 4 → gcd = 2, m/g = 1 (нечетное), p/g = 2 (четное) → встреча невозможна.

Код на Python

• Вход: два целых числа m и p (минуты до фонтана от каждого дома).
• Выход: минимальное время встречи в минутах, или -1 если встреча невозможна.

import sys
import math

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    m, p = map(int, data[:2])

    g = math.gcd(m, p)
    m1 = m // g
    p1 = p // g

    # встреча возможна только если m1 и p1 оба нечетные
    if (m1 & 1) and (p1 & 1):
        t = m * p // g  # lcm(m, p)
        print(t)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Как тестировать

• Ввод: 3 5 Вывод: 15
• Ввод: 2 4 Вывод: -1

Если нужна форматированная версия вывода (например, сначала “YES” и потом время), можно легко адаптировать код: заменить вывод на печать "YES" и t, или "NO" вместо -1.