Встреча у фонтана Ограничение по времени: 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 минут, где он и встретится с Машей. Во втором примере Маша успеет дойти до фонтана и вернуться домой, пока Паша идёт до фонтана. Пока Паша возвращается домой, Маша опять проделывает путь до фонтана и обратно. Каждый раз, когда Паша оказывается у фонтана или у своего дома, Маша находится у своего дома, поэтому они не смогут встретиться. Реши и сделай информатисескую формулу

Задача сводится к тому, чтобы понять, когда оба будут у фонтана одновременно, если они чередуют путь туда-обратно (дом → фонтан → дом → фонтан …) и начинают одновременно из своих домов. 1) Математическая модель - Машу времени достижения фонтана: 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 — время до первой встречи. 2) Условия существования решения Пусть d = gcd(m, p). Совместность двух конгруэнций t ≡ m (mod 2m) и t ≡ p (mod 2p) эквивалентна тому, что m − p делится на gcd(2m, 2p) = 2d. То есть: - если (m − p) не делится на 2d, ответ -1; - иначе решение существует. 3) Как посчитать минимальное 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-битные целые. 4) Пример 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 5) Алгоритм решения (чистая формула) - 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 6) Псевдокод 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 7) Что это значит на практике - Иногда встреча невозможна, например m = 1, p = 2 → нет решения, ответ -1. - Если решение есть, минимальное время встречи можно вычислить за логарифмическое время по gcd и обратному элементу (быстро даже для больших чисел). Если хотите, могу привести конкретный код на вашем любимом языке (C++, Python, Java, etc.) с реализацией расширенного алгоритма Евклида для нахождения modular_inverse.