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

Кратко понятие задачи

• Маше и Паше нужно одновременно оказаться у фонтана.
• Маше до фонтана нужно m минут, Паше — p минут.
• Они отправляются одновременно, затем идут к фонтану, если никого там нет — возвращаются домой, и так повторяют путь туда/обратно, пока не встретятся у фонтана.
• Машина времени на встречу — минимальное t > 0 такое, что оба одновременно находятся у фонтана.

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

• Маша оказывается у фонтана в моменты времени t ∈ {m, 3m, 5m, ...} то есть t ≡ m (mod 2m).
• Паша оказывается у фонтана в моменты времени t ∈ {p, 3p, 5p, ...} то есть t ≡ p (mod 2p).
• Нужно найти наименьшее t, удовлетворяющее системе конгруэнций: t ≡ m (mod 2m) t ≡ p (mod 2p)
• Такого t может не быть. Необходимо проверить совместимость по китайской теореме о остатках: существуют решения iff m ≡ p (mod gcd(2m, 2p)), то есть iff (p - m) делится на d = gcd(2m, 2p) = 2 * gcd(m, p).
• Если решения нет — ответ -1. Если есть — вычисляем наименьшее t через CRT.

Пошаговое решение (алгоритм)

1. g0 = gcd(m, p)
2. d = 2 * g0
3. если (p - m) % d != 0, вывести -1
4. Пусть a = 2m, b = 2p. Разделим: ap = a / d, bp = b / d, c = (p - m) / d
5. Нужно найти k такое, что ap * k ≡ c (mod bp). Так как gcd(ap, bp) = 1, существует обратная к ап по bp.
6. inv = модульный обратный ап по bp
7. k = (c mod bp) * inv mod bp
8. искомое время t = m + a * k
9. вывести t

Пояснение по корректности

• В шаге 3 условие говорит: конгруэнции несовместны, значит встреча никогда не произойдёт.
• В противном случае, после приведения к канонической форме, мы находим минимальный k в диапазоне [0, bp-1], что даёт минимальное t, удовлетворяющее обе конгруэнции. Так мы получаем первую встречу у фонтана.

Пример

• Пример 1: m = 3, p = 5 g0 = gcd(3,5) = 1, d = 2 (p - m) = 2 делится на 2 → решение есть a = 6, b = 10, ap = 3, bp = 5, c = 1 inv(3 mod 5) = 2 (потому что 32 ≡ 1 (mod 5)) k = (1 * 2) mod 5 = 2 t = m + ak = 3 + 6*2 = 15 Ответ: 15

• Пример 2: m = 1, p = 2 g0 = gcd(1,2) = 1, d = 2 (p - m) = 1 не делится на 2 → встреча не произойдёт Ответ: -1

Временная сложность

• Основные операции — вычисление gcd и единичной modular inverse, всё это делает за O(log min(m, p)).
• Используемые типы: 64-битные целые (long long). Значение может достигать порядка 2m·bp, но вписывается в 64 бит.

Пример кода (C++17, 64-битные целые) #include <bits/stdc++.h> using namespace std;

using int64 = long long;

int64 extgcd(int64 a, int64 b, int64 &x, int64 &y) { if (b == 0) { x = 1; y = 0; return a; } int64 x1, y1; int64 g = extgcd(b, a % b, x1, y1); x = y1; y = x1 - (a / b) * y1; return g; }

int64 modinv(int64 a, int64 m) { int64 x, y; int64 g = extgcd(a, m, x, y); if (g != 1) return -1; // inverse doesn't exist, but в нашем случае он всегда существует x %= m; if (x < 0) x += m; return x; }

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

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

int64 g0 = std::gcd(m, p);
int64 d = 2 * g0;
int64 diff = p - m;

if (diff % d != 0) {
    cout << -1 << "\n";
    return 0;
}

int64 a = 2 * m;
int64 b = 2 * p;
int64 ap = a / d;
int64 bp = b / d;
int64 c = diff / d;

int64 inv = modinv((ap % bp + bp) % bp, bp);
// bp >= 1 и gcd(ap, bp) = 1, так что inv существует
int64 k = (( (c % bp + bp) % bp) * inv) % bp;
int64 t = m + a * k;

cout << t << "\n";
return 0;

}

Как применять на реальных задачах

• Введите m и p, получите ответ:
  • если -1, значит никогда не встретятся у фонтана
  • иначе — минимальное время в минутах с момента выхода из домов, когда они встретятся на фонтане.