中国剩余定理

中国剩余定理 (Chinese Remainder Theorem, CRT) 的相关内容。

设 是两两互质的整数，， 是同余方程 的一个解。

对于任意的 个整数 ，方程组

有整数解，为 。

证明

因为 ，所以 。设 ，因为 ，所以 ，即最后答案对所有方程组成立。

实现

都可以直接算出，而 是同余方程的解。

因为 两两互质，所以 与 互质。由裴蜀定理得

即

因此只需通过扩展欧几里得算法求出 。 即为 的一个解。

洛谷 P1495【模板】中国剩余定理（CRT）/ 曹冲养猪

#include <cstdio>

typedef long long ll;

const int N = 13;
ll n, p[N], a[N];
ll m = 1, M[N], t[N];
ll ans;

int main() {
  scanf("%lld", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld %lld", &p[i], &a[i]);
    m *= p[i];
  }
  for (int i = 1; i <= n; i++) {
    M[i] = m / p[i];
    ll x, y;
    ExGcd(M[i], p[i], x, y);
    t[i] = x < 0 ? x + p[i] : x;
    ans += a[i] * M[i] * t[i];
  }
  printf("%lld\n", ans % m);
  return 0;
}