中国剩余定理（CRT）学习笔记

十月 03, 2019 2496

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

简介

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

——百度百科

公式

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

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) ）
那么该同余方程的一个解为
MATHJAX-SSR-602
通解为 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
60
//
//  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;
}