Встреча у фонтана Ограничение по времени: 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. - Они уходят одновременно, потом, если к fountain никого нет, возвращаются домой и снова отправляются к фонтану, пока не встретятся у фонтана. - Встреча у фонтана возможна только тогда, когда оба будут у фонтана в одно и то же время. Пошаговое решение 1) Времена прибытия к фонтану у каждого - Машa находится у фонтана в моменты времени t, удовлетворяющие t ≡ m (mod 2m). Это потому, что она достигает фонтана за m минут, затем возвращается домой за m минут, и так далее. - Пашa находится у фонтана в моменты времени t, удовлетворяющие t ≡ p (mod 2p). Задача сводится к нахождению наименьшего общего времени t, удовлетворяющего одновременно обе мод-коррекции: t ≡ m (mod 2m) t ≡ p (mod 2p) 2) Условия существования решения Обозначим g = gcd(m, p). Пусть m = g·a, p = g·b, где gcd(a, b) = 1. Из теории систем конгруэнций с не взаимно простыми модулями существование решения возможно только если a и b имеют одинаковую чётность. Но так как gcd(a, b) = 1, они либо оба нечетны, либо один чётный и другой нечётный. В итоге решение существует только если оба a и b нечётны, то есть: m/g и p/g — обе нечетные. Если условие не выполняется, ответ = -1. 3) Как найти минимальное время t (CRT) Пусть: - n1 = 2m, a1 = m - n2 = 2p, a2 = p - d = gcd(n1, n2) = 2g Если (a2 − a1) не делится на d, решения нет (но при выполнении условия выше это не происходит). Пусть: - n1' = n1/d = m/g = a - n2' = n2/d = p/g = b - c = (a2 − a1)/d = (p − m)/(2g) Необходимо найти k такое, что n1'·k ≡ c (mod n2'). Так как gcd(n1', n2') = 1, можно взять обратную величину inv(n1' mod n2') и вычислить k ≡ c · inv(n1' mod n2') (mod n2'). Тогда минимальное неотрицательное решение: t = a1 + n1 · k Примечание по вычислениям: - Все арифметические промежуточные значения можно держать в 64-битах (макс примерно до 2·10^18). - Чтобы корректно учесть возможную отрицательность c, вычисляйте k по модулю n2' и нормализуйте по положительным остаткам. 4) Пример m = 3, p = 5 - g = gcd(3,5) = 1 - m/g = 3 (нечное), p/g = 5 (нечное) → решение существует - n1 = 6, a1 = 3; n2 = 10, a2 = 5; d = 2 - n1' = 3, n2' = 5, c = (5 − 3)/2 = 1 - inv(3 mod 5) = 2 (п because 3·2 ≡ 1 mod 5) - k ≡ 1 · 2 ≡ 2 (mod 5) - t = a1 + n1·k = 3 + 6·2 = 15 Ответ: 15 5) Ещё пример m = 2, p = 4 - g = gcd(2,4) = 2 - m/g = 1, p/g = 2 → один из них чётный, значит решение не существует - Ответ: -1 6) Алгоритм (для реализации) - Ввести m, p (тип long long). - g = gcd(m, p). - Если (m/g) и (p/g) не оба нечетные, вернуть -1. - d = 2*g - n1 = 2*m, a1 = m - n2 = 2*p, a2 = p - n1' = n1 / d, n2' = n2 / d, c = (a2 - a1) / d - inv = модульный обратный коэффициент к n1' по mod n2' (находитc через расширенный НОД; так как gcd(n1', n2') = 1, обратный есть) - k = ((c mod n2') * inv) mod n2' (обеспечиваем положительный остаток) - t = a1 + n1 * k - вернуть t 7) Что это даёт - Если m/g и p/g оба нечетны, встреча произойдёт, и время t можно найти указанным способом. - Время t может быть очень большим, но не превосходит порядка 2·m·p, что помещается в 64-битное целое. Итого - Условия существования: m/g и p/g должны быть обе нечётные. - Время встречи: наименьшее решение системы t ≡ m (mod 2m), t ≡ p (mod 2p) вычисляется через CRT в линейном времени (логарифм по числу разрядов). Если хотите, могу привести готовую короткую реализацию на C++ (с использованием расширенного НОД для modular inverse) или привести пошаговый разбор под конкретные числа.