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

Классная задача про Машу и Пашу: они идут к фонтану, потом возвращаются домой и снова идут к фонтану, пока не встретятся именно у фонтана. Нам дано, что Маша идёт до фонтана m минут, Паша — p минут. Вопрос: встретятся ли они в парке у фонтана? Если да, через сколько минут от начала движения?

Вот понятное решение пошагово.

1. Простейшая модель времени прихода к фонтану

• Маша добирается до фонтана за m минут, затем идёт обратно к дому (ещё m минут), снова идёт к фонтану (ещё m), и так далее.
  • Время, когда Маша оказывается у фонтана: t = m, 3m, 5m, 7m, ... то есть все нечетные множители m: t принадлежит прогрессии m + 2m·k, где k = 0,1,2,...
• Паша аналогично: он приходит к фонтану за p минут, потом возвращается домой (ещё p минут), снова идёт к фонтану (ещё p), и так далее.
  • Время, когда Паша оказывается у фонтана: t = p, 3p, 5p, 7p, ... то есть t принадлежит прогрессии p + 2p·k.

2. Условие существования встречи у фонтана Мы ищем число времени t, которое одновременно относится к обеим прогрессиям:

• t ≡ m (мод 2m)
• t ≡ p (мод 2p)

Такое t существует и будет минимальным положительным временем, если и только если следующие условие выполняется:

• p − m делится на gcd(2m, 2p) = 2·gcd(m, p).

Проще говоря:

• Пусть d = gcd(m, p).
• Тогда существует общие время встречи, если m/d и p/d имеют одну и ту же чётность (то есть оба нечетны). В этом случае встреча произойдёт, и её время можно найти, используя китайскую теорему для систем congruences.

Если же m/d и p/d имеют разную чётность, встреча у фонтана никогда не произойдёт.

3. Как посчитать минимальное время встречи, если она есть Если встреча возможна, минимальное t можно найти как решение системы:

• t = m + 2m·a
• t = p + 2p·b для некоторых неотрицательных целых a и b.

Читается так: нужно найти целое a такое, чтобы m + 2m·a ≡ p (мод 2p). Пусть

• g = gcd(2m, 2p) = 2·gcd(m, p)
• d0 = p − m

Если d0 не делится на g — решения нет (соответственно встреча не happens; см. пункт 2).

Если делится — можно привести задачу к меньшим числам:

• Пусть m1 = 2m / g, p1 = 2p / g, d1 = (p − m) / g.
• Тогда нужно найти a так, чтобы m1·a ≡ d1 (мод p1).
• Так как gcd(m1, p1) = 1, модуль можно взять с помощью обратного элемента: найдите обратный модуля m1 по отношению к p1, назовём его inv.
• Тогда a ≡ d1·inv (мод p1).
• Берём то значение a в диапазоне 0..(p1−1), подставляем в t = m + 2m·a — получаем минимальное t0.

Коротко:

• Вычисляем g = gcd(2m, 2p) = 2·gcd(m, p).
• Если (p − m) делится на g, решение есть и можно найти через CRT (как выше); иначе решения нет.
• Если m/d и p/d оба нечётны, то решение есть и его можно найти любым способом решений CRT.

4. Несколько наглядных примеров

• Пример 1: m = 3, p = 5
  • gcd(3,5) = 1, m/d = 3, p/d = 5, оба нечётны → встреча возможна.
  • Время минимальной встречи: t = 15 минут (Маша приходит в фонтана в 3, 9, 15,...; Паша в 5, 15, 25,...; пересечение — 15).
• Пример 2: m = 2, p = 3
  • gcd(2,3) = 1, m/d = 2 (чётно), p/d = 3 (нечётно) → разные чётности → встреча не произойдёт.
  • Если посмотрите на расписания: Маша у фонтана в 2, 6, 10, 14,...; Паша в 3, 9, 15,... — пересечения нет.

5. Как это объяснить школьнику (пояснение без сложной арифметики)

• Представьте часы: Маше и Паше нужно одновременно оказаться у фонтана.
• Машина времени: Маша приходит к фонтану через m минут, затем каждые 2m минут снова приходит; так же и Паша через p минут и каждые 2p минут после этого.
• Мы ищем момент, когда оба цикла совпадут.
• Важный вывод: это совпадение возможно, если после сокращения общего делителя m и p до их «несимпотных» частей (то есть m/d и p/d), обе части окажутся нечётными. Если да — момент совпадения найдётся; если нет — не найдётся.

6. Коротко: что можно записать в ответ

• Если встреча возможна: да, встретятся у фонтана через t0 минут. t0 можно найти как решение системы congruences t ≡ m (mod 2m) и t ≡ p (mod 2p) (обычно через CRT).
• Если встреча невозможна: нет, они встретиться не смогут.

7. Полезные советы

• Чтобы быстро проверить возможность встречи, достаточно вычислить d = gcd(m, p). Если (m/d) и (p/d) оба нечётны, встреча есть; иначе — нет.
• Если нужно найти точное время, используйте метод CRT как описано выше (или удобно вычислить через программу/калькулятор, который умеет решать системы конгруэнций).

Если хотите, могу подставить ваши конкретные значения m и p и посчитать минимальное время t0, либо показать два варианта решения: численный пример и общее доказательство.