Китайская теорема об остатках (CRT): как объединить систему сравнений x ≡ r_i (mod m_i)?
Дана система: x ≡ r1 (mod m1), x ≡ r2 (mod m2), ... с попарно взаимно простыми модулями. Нужно найти единственное x по модулю произведения. Знаю, что это китайская теорема об остатках, но не понимаю, как технически собрать ответ и где переполнение.
2 ответа
CRT для двух сравнений x ≡ r1 (mod m1), x ≡ r2 (mod m2) при gcd(m1, m2) = 1. Ищем x в виде x = r1 + m1·t. Подставляем во второе: r1 + m1·t ≡ r2 (mod m2), откуда t ≡ (r2 - r1)·m1^{-1} (mod m2). Обратный m1^{-1} mod m2 находим расширенным Евклидом.
// объединяет (r1, m1) и (r2, m2), gcd(m1,m2)=1, в (r, m1*m2)
pair<long long,long long> crt(long long r1, long long m1, long long r2, long long m2) {
long long x, y;
ext_gcd(m1, m2, x, y); // x = m1^{-1} mod m2
long long mod = m1 * m2;
__int128 t = ((__int128)(r2 - r1) * ((x % m2 + m2) % m2)) % m2;
if (t < 0) t += m2;
long long r = (r1 + (long long)((__int128)m1 * t % mod)) % mod;
return {(r % mod + mod) % mod, mod};
}
Для системы из многих сравнений сворачивай их попарно слева направо. Сложность — O(k log M) на k сравнений. Главная грабля — переполнение: произведение m1·t и сам mod = m1·m2 легко вылезают за long long, поэтому промежуточные умножения делай через __int128. Также нормализуй остатки в [0, m) (видно по (... % m + m) % m).
Если модули не взаимно простые, обычная CRT не применяется напрямую — есть обобщённая версия. Для пары (r1, m1), (r2, m2) решение существует тогда и только тогда, когда (r1 - r2) делится на g = gcd(m1, m2); тогда новый модуль — lcm(m1, m2). Реализуется через расширенный Евклид, который заодно даёт g. Это нужно в задачах, где модули произвольные (например, периоды нескольких процессов). Если в условии явно «попарно взаимно простые» — хватает простой версии выше.