Встреча у фонтана Ограничение по времени: 0.5 секунды Маша и Паша живут на одной улице, и их дома разделены только парком, в котором друзья любят гулять. В центре парка есть…
Встреча у фонтана Ограничение по времени: 0.5 секунды Маша и Паша живут на одной улице, и их дома разделены только парком, в котором друзья любят гулять. В центре парка есть красивый фонтан, у которого Маша и Паша хотят сегодня встретиться. Известно, что Маша идёт до фонтана m минут, Паша — p минут. Выйти из домов они договорились одновременно, также друзья решили приходить к фонтану и, если там никого нет, идти обратно к дому, а затем снова разворачиваться, пока в итоге не случится встреча у фонтана. Помогите друзьям понять, смогут ли они встретиться в парке у фонтана, и если да, то сколько минут пройдёт с момента выхода из домов до их встречи. Формат входных данных Первая строка содержит целое число m (1⩽m⩽109) — время в минутах, которое требуется Маше, чтобы дойти от дома до фонтана. Вторая строка содержит целое число p (1⩽p⩽109) — время в минутах, которое требуется Паше, чтобы дойти от дома до фонтана. Формат выходных данных Выведите одно целое число — время, через которое Маша и Паша смогут встретиться у фонтана, если выйдут из домов одновременно, или −1, если этого никогда не случится. Обратите внимание на то, что значение ответа в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#). Система оценки Решения, правильно работающие, когда m и p не превосходят 103, будут оцениваться в 30 баллов. Решения, правильно работающие, когда ответ не превосходит 109, будут оцениваться в 60 баллов. Замечание Здесь и далее все временные отметки даются относительно начала движения, т. е. выхода из дома. В первом примере из условия Маша придёт к фонтану через 3 минуты, развернётся и пойдёт назад. Паша придёт к фонтану через 5 минут и отправится домой. Через 6 минут Маша доберётся до дома, вновь окажется у фонтана через 9 минут, опять не найдёт Пашу, развернётся и пойдёт домой. В следующий раз она будет у фонтана через 15 минут. Паша же дойдёт до дома через 10 минут и вернётся к фонтану через 15 минут, где он и встретится с Машей. Во втором примере Маша успеет дойти до фонтана и вернуться домой, пока Паша идёт до фонтана. Пока Паша возвращается домой, Маша опять проделывает путь до фонтана и обратно. Каждый раз, когда Паша оказывается у фонтана или у своего дома, Маша находится у своего дома, поэтому они не смогут встретиться. Реши и сделай информатисескую формулу
Задача сводится к тому, чтобы понять, когда оба будут у фонтана одновременно, если они чередуют путь туда-обратно (дом → фонтан → дом → фонтан …) и начинают одновременно из своих домов.
- Математическая модель
- Машу времени достижения фонтана: m минут.
- Пашу времени достижения фонтана: p минут.
- Время, когда Машa находится у фонтана, равно m, 3m, 5m, … то есть t ≡ m (mod 2m).
- Время, когда Паша находится у фонтана, равно p, 3p, 5p, … то есть t ≡ p (mod 2p).
Поиск минимального времени встречи сводится к решению системы двух конгруэнций:
- t ≡ m (mod 2m)
- t ≡ p (mod 2p)
Если такая система несовместима, встреча никогда не произойдёт, ответ -1. Если совместима, минимальное положительное t — время до первой встречи.
- Условия существования решения Пусть d = gcd(m, p). Совместность двух конгруэнций t ≡ m (mod 2m) и t ≡ p (mod 2p) эквивалентна тому, что m − p делится на gcd(2m, 2p) = 2d. То есть:
- если (m − p) не делится на 2d, ответ -1;
- иначе решение существует.
- Как посчитать минимальное t (формула и пошагово) Упростим задачу. Пусть:
- d = gcd(m, p)
- m1 = m / d
- p1 = p / d
Из условия solvности следует, что p1 − m1 чётно, т.е. s = (p1 − m1) / 2 — целое число.
Тогда задача сводится к решению удачного единичного конгруэнтного уравнения: m1 x ≡ s (mod p1) Так как gcd(m1, p1) = 1, уравнение имеет единственный раствор modulo p1: x ≡ inv(m1 mod p1) * s (mod p1), где inv(a mod n) — обратный элемент к a по модулю n (остаток от деления, который удовлетворяет a * inv ≡ 1 (mod n)). После нахождения x минимального неотрицательного значения в диапазоне [0, p1−1], получаем время встречи: t = m + 2m x = m (1 + 2x).
Замечания:
- Если p1 = 1, то модуль равен 1 и x = 0, и t = m.
- Все вычисления требуют 64-разрядных целых (потенциально до примерно 2 * 10^18), поэтому использовать 64-битные целые.
- Пример m = 3, p = 5
- d = gcd(3,5) = 1
- 2d = 2, (m − p) = −2, делится на 2 → решение существует
- m1 = 3, p1 = 5
- s = (5 − 3)/2 = 1
- inv(m1 mod p1) = inv(3 mod 5) = 2 (потому что 3*2 ≡ 1 (mod 5))
- x ≡ 2 * 1 ≡ 2 (mod 5) → x = 2
- t = m (1 + 2x) = 3 (1 + 4) = 15 Ответ: 15
- Алгоритм решения (чистая формула)
- d = gcd(m, p)
- если (m − p) % (2d) != 0 → вывести -1
- иначе:
- m1 = m / d
- p1 = p / d
- если p1 == 1 → x = 0 иначе: s = (p1 − m1) / 2 (целое число) inv = modular_inverse(m1 mod p1, p1) // обратный элемент к m1 по модулю p1 x = (s mod p1) * inv mod p1
- t = m * (1 + 2 * x)
- вывести t
Псевдокод read m, p (int64) d = gcd(m, p) if (m - p) % (2*d) != 0: print -1 else: m1 = m / d p1 = p / d if p1 == 1: x = 0 else: s = (p1 - m1) / 2 inv = mod_inverse(m1 % p1, p1) // расширенный алгоритм Евклида x = ( (s % p1) * inv ) % p1 t = m * (1 + 2 * x) print t
Что это значит на практике
- Иногда встреча невозможна, например m = 1, p = 2 → нет решения, ответ -1.
- Если решение есть, минимальное время встречи можно вычислить за логарифмическое время по gcd и обратному элементу (быстро даже для больших чисел).
Если хотите, могу привести конкретный код на вашем любимом языке (C++, Python, Java, etc.) с реализацией расширенного алгоритма Евклида для нахождения modular_inverse.
