中国剩余定理

CRT（模数两两互质）

求解一元线性同余方程组（ $n_{1}, \dots, n_{k}$ 两两互质）：

⎩ ⎨ ⎧ x \equiv a_{1} (mod n_{1}) x \equiv a_{2} (mod n_{2}) ⋮ x \equiv a_{k} (mod n_{k})

步骤：

计算 $n = \prod n_{i}$
对每个 $i$ ，计算 $m_{i} = n / n_{i}$ ，求 $m_{i}$ 在模 $n_{i}$ 下的逆元 $m_{i}^{- 1}$ ，得 $c_{i} = m_{i} \cdot m_{i}^{- 1}$
解： $x \equiv \sum a_{i} c_{i} (mod n)$

LL crt(int k, LL* a, LL* r) {
  LL n = 1, ans = 0;
  for (int i = 1; i <= k; i++) n = n * r[i];
  for (int i = 1; i <= k; i++) {
    LL m = n / r[i], b, y;
    exgcd(m, r[i], b, y);
    ans = (ans + a[i] * m * b % n) % n;
  }
  return (ans % n + n) % n;
}

EXCRT（模数不互质）

两两合并。设两个方程 $x \equiv a_{1} (mod m_{1})$ 、 $x \equiv a_{2} (mod m_{2})$ ：

转化为 $m_{1} p - m_{2} q = a_{2} - a_{1}$ ，用 EXGCD 求解。若 $g cd (m_{1}, m_{2}) ∤ (a_{2} - a_{1})$ 则无解。合并后模数为 $lcm (m_{1}, m_{2})$ 。

LL excrt(int k, LL* a, LL* m) {
  LL ans = a[1], M = m[1];
  for (int i = 2; i <= k; i++) {
    LL x, y, d = exgcd(M, m[i], x, y);
    if ((a[i] - ans) % d) return -1;
    x = (a[i] - ans) / d * x % (m[i] / d);
    ans += x * M;
    M = M / d * m[i];
    ans = (ans % M + M) % M;
  }
  return ans;
}

练习题目

题目	描述
P1495 曹冲养猪	CRT 模板
P4777 【模板】扩展中国剩余定理	EXCRT 模板
P3868 [TJOI2009] 猜数字	CRT 应用

多平台练习

RootStack

探索

中国剩余定理

中国剩余定理

CRT（模数两两互质）

EXCRT（模数不互质）

练习题目

相关链接

多平台练习

关系图谱

目录

反向链接