这部分内容介绍了同余方程，类Euclid算法等内容

线性同余方程

对于线性同于方程 ax≡c( mod b)ax \equiv c (\bmod b)

定理1，方程 ax+by=cax+by = c 等价于方程 ax≡c( mod b)ax \equiv c(\bmod b)
有整数解的充要条件是 gcd(a,b)∣c\textbf{gcd}(a, b) \mid c

algorithm\textbf{algorithm}
用扩展Euclid算法求解出一组 x0,y0x_0, y_0，满足 ax0+by0=gcd(a,b)ax_0 + by_0 = \textbf{gcd}(a, b)
两边同时除以 gcd(a,b)\textbf{gcd}(a, b)，再 ×c\times c
acx0/gcd(a,b)+bcy0/gcd(a,b)=cacx_0 / \text{gcd}(a, b) + bcy_0/ \text{gcd}(a, b) = c

cx0gcd(a,b),cy0gcd(a,b)\frac{cx_0}{\text{gcd}(a, b)}, \quad \frac{cy_0}{\text{gcd}(a, b)}

定理2， 若 gcd(a,b)=1\text{gcd}(a, b) = 1，并且 x0,y0x_0, y_0 是方程
ax+by=cax + by = c 的一组解，那么方程的任意解可以表示为
∀t∈Z,x=x0+bt,y=y0−at\forall t \in \mathbb{Z}, \quad x = x_0 + bt, y = y_0 - at

因为此时 tt 为任意整数都可以成立，这个时候我们可以求出方程的所有解
但实际问题中，我们只需要求解一个最小整数解就可以了

实际上，根据定理1，我们可以把一般解式表示为

x=cx0gcd(a,b)+k⋅bgcd(a,b)y=cy0gcd(a,b)−k⋅agcd(a,b)∀k∈Z\begin{gathered} x = \frac{cx_0}{\text{gcd}(a, b)} + k \cdot \frac{b}{\text{gcd}(a, b)} \\ y = \frac{cy_0}{\text{gcd}(a, b)} - k \cdot \frac{a}{\text{gcd}(a, b)} \\ \forall k \in \mathbb{Z} \end{gathered}

注意到 kk 可以取任意整数
方程的通解实际上是

 mod bgcd(a,b)≡x≡cx0gcd(a,b)\bmod \frac{b}{\text{gcd}(a, b)} \equiv x \equiv \frac{cx_0}{\text{gcd}(a, b)}

就是一类同余数， mod bgcd(a,b)\bmod \frac{b}{\text{gcd}(a, b)}余数是

cx0gcd(a,b)\frac{cx_0}{\text{gcd}(a, b)}

最小的数，一般取 k=1k = 1，此时对一个特解 xx

t=bgcd(a,b),x=(x mod t+t) mod tt = \frac{b}{\text{gcd}(a, b)}, \quad x = (x \bmod t + t) \bmod t

LOJ2605 同余方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ll a, b;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }

    ll d = exgcd(b, a%b, x, y);
    ll z = x; x = y; y = z - (a/b)*y;
    return d;
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> a >> b;

    ll x, y;
    exgcd(a, b, x, y);
    ll res = (x % b + b) % b;
    cout << res << endl;
}

扩展Euclid算法求解线性同余方程

ax≡c( mod b)ax \equiv c(\bmod b)
也就是 ax+by=cax + by = c 方程的解，要求求出一个最小的 xx

  • algorithm\textbf{algorithm}
    • d=exgcd(a,b,x,y)⇒get xd=\textbf{exgcd}(a, b, x, y) \Rightarrow \text{get }x
      计算出一个特解 xx
    • c mod d≠0c \bmod d \neq 0，没有解
      else k=c/d\textbf{else} \ k = c/d
      x←(x⋅k) mod b,y←(y⋅k) mod bx \leftarrow (x \cdot k) \bmod b, \quad y \leftarrow (y \cdot k) \bmod b
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a%b, x, y);
    ll z = x; x = y; y = z - (a/b) * y;
    return d;
}

bool liEu(ll a, ll b, ll c, ll &x, ll &y) {
    ll d = exgcd(a, b, x, y);
    if (c % d) return 0;

    int k = c/d;
    x = (x * k) % b;
    y = (y * k) % b;
    return 1;
}

中国剩余定理

CRT01
CRT02

mim_i 不再两两互质情况下的中国剩余定理

POJ2891
POJ2891
假设解完前 kk 个线性同余方程之后得到的特解是 xx
m=lcm(m1,m2,⋯ ,mk)m = \textbf{lcm}(m_1, m_2, \cdots , m_k)
通解可以表示成 x+km(k∈Z)x + km (k \in \mathbb{Z})
最小非负整数解为 x mod mx \bmod m

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
typedef unsigned long long ull;
int n;

inline ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a%b, x, y);
    ll z = x; x = y; y = z - (a/b) * y;
    return d;
}

void solve(int n) {
    ll a, r;
    cin >> a >> r;
    ll ans = r, lcm = a;
    bool fl = true;

    n--;
    while (n--) {
        cin >> a >> r;

        // exgcd
        r = (r - ans % a + a) % a;
        ll x, y, x2;
        ll d = exgcd(lcm, a, x, y);
        if (r % d) fl = false;
        else x2 = x * (r/d) % a;

        ans += x2 * lcm;
        // update lcm, and get min ans
        lcm = (lcm / d) * a;
        ans = (ans % lcm + lcm) % lcm;
    }

    if (fl) cout << ans << endl;
    else cout << "-1" << endl;
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    while (cin >> n) {
        init();

        solve(n);
    }
}

CRT算法图解

CRTalgo

高次同余方程