核心概述
中国剩余定理（CRT）：求解同余组 x ≡ r_i (mod m_i)。当模数两两互质时存在唯一解（模 M=∏m_i）；一般情形需判定可解性并合并为 x ≡ R (mod L)，L 为各模的 lcm。常用扩展欧几里得逐步合并，复杂度 O(k log M)。
原文引述
Description: Solve x ≡ r_i (mod m_i). Returns a single congruence x ≡ R (mod L) or reports no solution. Uses extended Euclid to merge constraints, supports non-coprime moduli. Time: O(k log M) where M is the product/lcm scale
展开阐述
-
函数/接口（据实现）
- pair<ll,ll> crt(const vector
& r, const vector & m) - pair<ll,ll> crt(ll r1, ll m1, ll r2, ll m2)
- 语义：返回 {R, L}，使解为 x ≡ R (mod L) 且 0 ≤ R < L；若无解则返回 {0, -1}。
- pair<ll,ll> crt(const vector
-
核心思路（扩展欧几里得合并同余）
- 合并两式：
- 给定 x ≡ r1 (mod m1)，x ≡ r2 (mod m2)。
- 设 g = gcd(m1, m2)，若 (r2 − r1) % g ≠ 0 则无解。
- 设 m1’ = m1/g，m2’ = m2/g，t = (r2 − r1)/g。
- 求 inv = (m1’)^{-1} mod m2’（用扩展欧几里得），令 k = (t · inv) mod m2’。
- 合并得到 R = r1 + k·m1，模数 L = lcm(m1, m2) = m1·m2’·g（实现中常写为 m1/g·m2）。
- 规范化 R 到 [0, L)。
- 多个同余：从初始 {R, L}={r0, m0} 起，依次与 (ri, mi) 合并；若任一步无解则整体无解。
- 合并两式：
-
输出语义
- {R, L}：所有解构成等价类 R + t·L（t∈Z），其中 L 为最终模数（lcm）。
- 无解以 L = −1 表示（据模板约定）。
-
复杂度
- 每次合并做一次 exgcd 与常数次取模，O(log max(m1, m2))；总体 O(k log M)。
-
使用与注意
- 互质特例：若 m_i 两两互质，则总有解，R 唯一（模 M=∏m_i）。
- 溢出：在计算 R 或 L 时可能超过 64 位，建议用 __int128 或配合090-数论-长整型模乘。
- 规范化输入：将 r_i 先规约到 [0, m_i) 以稳定可解性判断。
- 模逆需 gcd=1（在 m2’ 下）；一般情形无需预先求逆，直接用扩展欧几里得。
- 若仅需给定模 p 下的解，可先用 CRT 合并再对 p 取模（当 p|L 时注意唯一性）。