中国剩余定理(CRT)学习笔记

有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

简介

孙子定理是中国古代求解一次同余式组(见同余)的方法。是数论中一个重要定理。又称中国余数定理。

——百度百科

公式

孙子定理是用来求解这样的方程组的:

uBlVUJ.png

(我博客行间公式渲染好像有点问题……)

CRT 的使用条件是 $m_i$ 两两互质,$m_i$ 两两不互质需要使用 exCRT 即扩展中国剩余定理


首先定义 $M = \prod_{i = 1}^n m_i$,并设 $M_i = \lfloor {M \over {m_i}} \rfloor$,$t_i = M_i^{-1} \bmod M$(即$t_i$满足$M_i t_i \equiv 1 (\bmod M)$)
那么该同余方程的一个解为

通解为 $x = x_0 + i \times M$,最小非负整数解为 $(x_0 \bmod M + M) \bmod M$

如果有 $a < 0$ 的情况时要注意负数取模问题

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//
// CRT.cpp
// Debugging
//
// Created by HandwerSTD on 2019/10/3.
// Copyright © 2019 HandwerSTD. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define basketball(a,t,s,i) for (int a = t; a > s; a -= i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

typedef long long int lli;

int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }

lli k, a[10000 + 10], m[10000 + 10];

namespace ChinaRemainderTheorem {
lli exgcd(lli a, lli b, lli &x, lli &y) {
if (b == 0) { x = 1; y = 0; return a; }
lli g = exgcd(b, a % b, y, x);
y -= a / b * x;
return g;
}
lli CRT() {
lli X = 0, M = 1;
for (lli i = 1; i <= k; ++i) M *= m[i];
for (lli i = 1; i <= k; ++i) {
lli ti = 0, y = 0;
lli mmi = M / m[i];
exgcd(mmi, m[i], ti, y);
X = ((X + a[i] * mmi * ti) % M + M) % M;
}
return X < 0 ? (X + M) : X;
}
}

signed main() {
k = getll();
/// x === ai (mod mi)
rap (i, 1, k, 1) { m[i] = getll(); a[i] = getll(); }
printf("%lld\n", ChinaRemainderTheorem::CRT());
return 0;
}