Совмещение календарей — разбор

1. Идея

Нужно найти наименьшее неотрицательное число x, такое что одновременно выполняются два условия:

• x % m1 == a1
• x % m2 == a2

Так как m1 и m2 взаимно просты, решение существует и единственно по модулю m1 * m2.

Вместо прямого перебора удобно выразить все числа, подходящие под первое условие:

• x = a1 + m1 * k

Тогда осталось подобрать такое k, чтобы это число также удовлетворяло второму сравнению:

• a1 + m1 * k ≡ a2 (mod m2)

Отсюда:

• m1 * k ≡ a2 - a1 (mod m2)

Теперь нужно поделить на m1 по модулю m2, то есть найти обратный элемент к m1 по модулю m2.

2. Наблюдения

Наблюдение 1

Так как gcd(m1, m2) = 1, число m1 обратимо по модулю m2.

Это означает, что существует такое число inv, что:

• m1 * inv ≡ 1 (mod m2)

Наблюдение 2

Обратный элемент можно найти с помощью расширенного алгоритма Евклида.

Если он находит числа x и y такие, что:

• m1 * x + m2 * y = 1

то из этого сразу следует:

• m1 * x ≡ 1 (mod m2)

Значит, x — это и есть обратный элемент к m1 по модулю m2 (возможно, отрицательный, поэтому потом берём остаток по модулю m2).

Наблюдение 3

После нахождения обратного элемента получаем:

• k ≡ (a2 - a1) * inv (mod m2)

Тогда можно взять минимальный неотрицательный k, а ответ вычислить как:

• x = a1 + m1 * k

Именно это число будет наименьшим неотрицательным решением.

3. Алгоритм

1. Считать a1, m1, a2, m2.
2. С помощью расширенного алгоритма Евклида найти коэффициенты x, y из равенства:
   • m1 * x + m2 * y = gcd(m1, m2)
3. Так как gcd(m1, m2) = 1, число x задаёт обратный элемент к m1 по модулю m2.
4. Привести его к нормальному виду:
   • inv = x % m2
5. Вычислить разность остатков:
   • diff = (a2 - a1) % m2
6. Найти:
   • k = (diff * inv) % m2
7. Ответ:
   • answer = a1 + m1 * k
8. Вывести answer.

4. Почему это работает

Ищем число x, удовлетворяющее системе:

• x ≡ a1 (mod m1)
• x ≡ a2 (mod m2)

Из первого сравнения любое подходящее число имеет вид:

• x = a1 + m1 * k

Подставим во второе:

• a1 + m1 * k ≡ a2 (mod m2)

Переносим a1:

• m1 * k ≡ a2 - a1 (mod m2)

Так как m1 и m2 взаимно просты, у m1 есть обратный элемент inv по модулю m2, то есть:

• m1 * inv ≡ 1 (mod m2)

Умножим сравнение на inv:

• k ≡ (a2 - a1) * inv (mod m2)

Значит, если взять

• k = ((a2 - a1) * inv) % m2

то число

• x = a1 + m1 * k

точно удовлетворяет обоим условиям.

Почему это решение минимальное неотрицательное?

• k берётся в диапазоне от 0 до m2 - 1
• значит, x — это наименьшее число среди всех решений вида a1 + m1 * k, которое подходит по второму модулю
• все остальные решения отличаются на m1 * m2, поэтому это действительно минимальный неотрицательный ответ

5. Сложность

Расширенный алгоритм Евклида работает за O(log(min(m1, m2))).

Все остальные операции — константные.

Итого:

• время: O(log(min(m1, m2)))
• память: O(log(min(m1, m2))) из-за рекурсии

6. Код на C++17

#include <iostream>

using namespace std;

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

int main() {
    long long a1, m1, a2, m2;
    cin >> a1 >> m1;
    cin >> a2 >> m2;

    long long x, y;
    extended_gcd(m1, m2, x, y);

    long long inv = (x % m2 + m2) % m2;
    long long diff = (a2 - a1) % m2;
    if (diff < 0) diff += m2;

    long long k = (diff * inv) % m2;
    long long answer = a1 + m1 * k;

    cout << answer << '\n';
    return 0;
}

7. Код на Python 3

a1, m1 = map(int, input().split())
a2, m2 = map(int, input().split())

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

g, x, y = extended_gcd(m1, m2)

inv = x % m2
diff = (a2 - a1) % m2
k = (diff * inv) % m2
answer = a1 + m1 * k

print(answer)