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

Ключевая идея задачи

• Маша и Паша двигаются по очереди между домом и фонтаном. Они будут одновременно у фонтана в моменты времени, которые удовлетворяют двум условиям:
  • Маша прибывает к фонтану через каждые 2m минут, начиная с m: t ≡ m (mod 2m).
  • Паша прибывает к фонтану через каждые 2p минут, начиная с p: t ≡ p (mod 2p).
• Нужно найти первое время t, когда оба условия выполнены одновременно. Это задача CRT (китайская теорема об остатках) для нулевых congruences: t ≡ m (mod 2m) t ≡ p (mod 2p)

Когда решения нет

• Пусть n1 = 2m, n2 = 2p, a1 = m, a2 = p.
• Существует решение тогда и только для: (a2 − a1) делится на gcd(n1, n2).
• gcd(n1, n2) = gcd(2m, 2p) = 2 · gcd(m, p).
• Если (p − m) не делится на 2 · gcd(m, p), ответ −1.

Если решение есть

• Обозначим g = gcd(n1, n2) = 2 · gcd(m, p).
• Пусть n1' = n1 / g, n2' = n2 / g, c = (a2 − a1) / g.
• Нужно найти x such that n1' · x ≡ c (mod n2'). Так как gcd(n1', n2') = 1, существует обратная к n1' по модулю n2'.
• Найдём inv = обратную к n1' по модулю n2' (через расширенный алгоритм Евклида).
• Тогда x0 = (c · inv) mod n2', и искомое минимальное t0 даётся как t0 = a1 + n1 · x0.
• Вопрос времени удовлетворённости: t0 уже удовлетворяет и первым, и вторым условиям, и является наименьшим неотрицательным решением, т. к. t0 ≡ m (mod 2m) и t0 ≥ m, а также t0 ≡ p (mod 2p) и t0 ≥ p. Поэтому ответ — t0.

Пошагово

1. Ввести m, p. Пусть n1 = 2m, n2 = 2p, a1 = m, a2 = p.
2. g = gcd(n1, n2). Если (a2 − a1) mod g ≠ 0, вывести -1.
3. Иначе:
   • n1' = n1 / g, n2' = n2 / g, c = (a2 − a1) / g.
   • Найти inv = модульный обратный к n1' по модулю n2' (n1' · inv ≡ 1 (mod n2')).
   • x0 = (c mod n2') · inv mod n2'.
   • t0 = a1 + n1 · x0.
   • Вывести t0.
4. Типы: значения могут достигать порядка 2 · m · p, поэтому использовать 64-битные целые (int64/long long).

Пример

• Пусть m = 3, p = 5.
  • n1 = 6, n2 = 10, g = gcd(6, 10) = 2.
  • (p − m) = 2, делится на g = 2 → решение есть.
  • n1' = 3, n2' = 5, c = (5 − 3)/2 = 1.
  • inv = обратная к 3 по модулю 5 → 2 (потому что 3·2 ≡ 1 (mod 5)).
  • x0 = (1 · 2) mod 5 = 2.
  • t0 = a1 + n1·x0 = 3 + 6·2 = 15.
  • Ответ: 15 минут. Это согласуется с приведённым в условии примером.

Алгоритм со сложностью O(log(max(m, p)))

• Время работы в основном определяется вычислениями НОД и расширенным алгоритмом Евклида для модуля, так что это быстро даже для больших значений.

Пример реализации на C++ (используйте 64-битные типы)

• Этот код следует непосредственно вышеприведенному алгоритму и печатает t0 или -1.

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

// Расширенный gcd: возвращает g = gcd(a,b) и коэффициенты x, y такие, что a*x + b*y = g
struct EGCD { int64 g, x, y; };
EGCD extgcd(int64 a, int64 b) {
    if (b == 0) return {a, 1, 0};
    auto t = extgcd(b, a % b);
    return {t.g, t.y, t.x - (a / b) * t.y};
}

// Модульный обратный к a по модулю mod, при условии, что gcd(a, mod) = 1
int64 modinv(int64 a, int64 mod) {
    auto res = extgcd(a, mod);
    if (res.g != 1) return -1; // нет обратного
    int64 x = res.x % mod;
    if (x < 0) x += mod;
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int64 m, p;
    if (!(cin >> m)) return 0;
    if (!(cin >> p)) return 0;

    int64 n1 = 2 * m;
    int64 n2 = 2 * p;
    int64 a1 = m;
    int64 a2 = p;

    int64 g = std::gcd(n1, n2);

    if ((a2 - a1) % g != 0) {
        cout << -1 << "\n";
        return 0;
    }

    int64 n1p = n1 / g;
    int64 n2p = n2 / g;
    int64 c = (a2 - a1) / g;

    // Найдём обратную к n1' по модулю n2'
    int64 inv = modinv((n1p % n2p + n2p) % n2p, n2p);
    // x0 = (c * inv) mod n2'
    int64 x0 = ( (__int128)( (c % n2p + n2p) % n2p ) * inv ) % n2p;
    if (x0 < 0) x0 += n2p;

    int64 t0 = a1 + n1 * x0;

    cout << t0 << "\n";
    return 0;
}

Кратко резюме

• Мы превратили задачу в системy двух конгруэнций: t ≡ m (mod 2m) и t ≡ p (mod 2p).
• Проверили существование решения через gcd(2m, 2p). Если нет — ответ −1.
• При наличии решения нашли минимальное t с помощью CRT, используя расширенный gcd для вычисления обратного элемента. -Ответ хранится в 64-битном целочисленном типе и может быть большим (в примере до порядка 2·10^18).