同余方程与二元一次不定方程

同余

定义

\(a\bmod m = b \bmod m\) 则称 \(a,b\) 对于模 \(m\) 同余，记为 \(a \equiv b \pmod m\)

等价于 \(m\) 整除 \((a-b)\)，即 \(m\mid(a-b)\)

同余方程

\(ax \equiv b \pmod m\)

已知 \(a,b,n\)，求解 \(x\)。
当且仅当 \(b\) 能被 \(a\) 和 \(n\) 的最大公约数整除时此方程有解
若 \(x_0\) 是方程的一个解，解集即为 \(\{ x_0+km /\gcd(a,m) | k\in \mathbb{Z} \}\)

有解证明：

对于线性同余方程 \(ax \equiv b\pmod m\) 可以转换为 \(ax+km=b,k\in \mathbb{Z}\)

设 \(d=\gcd(a,m)\)，若方程有解为 \(c\)， 则 \(m \mid (ac-b)\) ，从而 \(d\mid(ac-b)\)，又因为 \(d\mid a\)，即 \(d\mid ac\)，于是有 \(d\mid b\)，即 \(\gcd(a,m)\mid b\)

扩展欧几里得算法

前置知识

裴蜀定理

\[ \forall a,b, \exists x,y,ax+by=\gcd(a,b) \]

即 \(ax\equiv \gcd(a,b)\pmod b\)

用途

• 求解同余方程 \(ax \equiv \gcd(a,n) \pmod n\)
  • \(\forall a,b,\exists x,y,ax+by=\gcd(a,b)\) (裴蜀定理)
    即 \(ax\equiv \gcd(a,b) \pmod b\)。而 \(x,y\) 可以用扩展欧几里得算法求出

同时,逆元的定义也是一个同余方程,也就是说该法可以求模意义下的逆元

原理

对于方程 \(ax_1+by_1=\gcd (a,b)\)，由裴蜀定理可得一定存在一组 \(x_1,y_1\) 使得等式成立

于是分两类讨论

• \(b = 0\) 时，\(ax_1+by_1=a\)，显然 \(x_1 = 1, y_1 \in \mathbf R\)

• \(b \neq 0\) 时，利用四个未知量 \(x_1,y_1,x_2,y_2\) 列出两个方程 \[ \begin{cases} ax_1+by_1 = \gcd(a,b) = \gcd(b, a\bmod b) ① \newline bx_2+(a\bmod b)y_2 = \gcd(b, a \bmod b) = \gcd(a,b) = ax_1+by_1 ② \end{cases} \] 易得 \[ a \bmod b = a-\lfloor\frac{a}{b}\rfloor b \] 由此我们可以继续展开推导 \(②\) 式 \[ \begin{aligned} bx_2+(a\bmod b)y_2 &= ax_1+by_1 \newline bx_2+(a-\lfloor \dfrac{a}{b}\rfloor b)y_2 &= ax_1+by_1 \newline ay_2+b(x_2-\lfloor \dfrac{a}{b} \rfloor y_2) &= ax_1+by_1 \end{aligned} \]因此 \[ \begin{cases} x_1 = y_2 \newline y_1 = x_2-\lfloor \dfrac{a}{b} \rfloor y_2 \end{cases} \]

实现

函数 \(\operatorname{exgcd}(a,b,x,y)\)

采用递归实现，因此先判定递归边界，则 \(b=0\) 时到达边界，此时 \(x = 1, y = 0\)

未到边界，则先继续调用 \(\operatorname{exgcd}(b, a\bmod b, x, y)\) ，然后根据递归回溯得到的 \(x,y\) 得到 \(x_1, y_1\)，即

\[ \begin{cases} x_1 = y \newline y_1 = x-\lfloor \dfrac{a}{b} \rfloor y \end{cases} \]

返回到头为止。

求解 \(ax + by = c\) ，即 \(a \equiv c \pmod b\)

先判断是否有解，若 \(\gcd(a,b) \mid c\) 则有解（裴蜀定理） 然后利用 \(\operatorname{exgcd}\) 求解 \(ax_1 + by_1 = \gcd (a,b)\) 即得到一份特解 \(x = x_1 \times \frac{c}{\gcd(a,b)}, y = y_1 \times \frac{c}{\gcd(a,b)}\)

求通解，实质上是使 \(x,y\) 进行一定变换但等式依然成立。 易想到 \(x\) 下降时 \(y\) 上升，因此设：\(g = \gcd(a,b), i>j\)

\[ \begin{aligned} ax_i+by_i&=c \newline ax_j + by_j &= c \end{aligned} \newline \]

导一下式子，得

\[ \begin{aligned} ax_i+by_i &= ax_j + by_j \newline a(x_i - x_j) &= b(y_j - y_i) \newline \frac ag (x_i - x_j) &= \frac bg (y_j - y_i) \end{aligned} \newline \]

因为 \(g\) 是最大公因数，所以 \(\frac ag\) 与 \(\frac bg\) 互质。又因为方程中每一个字母都是整数，所以易得：\(\frac bg\) 是 \(x_i-x_j\) 的倍数，而 \(\frac ag\) 是 \(y_j - y_i\) 的倍数（即 \(- \frac ag\) 是 \(y_i - y_j\) 的倍数）

于是通解就推出来了

\[ \begin{cases} \mathbf X = \{x+\cfrac bg k \mid k\in\mathbf Z\} \newline \mathbf Y = \{y-\cfrac ag k \mid k\in\mathbf Z\} \end{cases} \]

关于最小正整数 \(x\)，求法如下：

• 情况 1：\(\gcd(a,b) = 1\)
  • 此时 \(\frac bg = 1\) ，则 \(x_{min} = x \bmod b\)
• 情况 2：\(\gcd(a,b)=g\neq 1\)
  • 想办法列出新方程（\(x,y\) 不变）\(a_1x+b_1y=c_1,\gcd(a_1,b_1)=1\)，即 \(a_1,b_1\) 互质
  • 容易想到 \(a_1 = \frac ag, b_1 = \frac bg\)，然后为了保证等式成立，\(c_1 = \frac cg\)
  • 显然直接化为了第一种情况，于是 \(x_{min} = x \bmod \frac b{\gcd(a,b)}\)

代码

题目描述

给定不定方程 \[ax+by=c\] 若该方程无整数解，输出 \(-1\)。
若该方程有整数解，且有正整数解，则输出其正整数解的数量，所有正整数解中 \(x\) 的最小值，所有正整数解中 \(y\) 的最小值，所有正整数解中 \(x\) 的最大值，以及所有正整数解中 \(y\) 的最大值。
若方程有整数解，但没有正整数解，你需要输出所有整数解中 \(x\) 的最小正整数值， \(y\) 的最小正整数值。

正整数解即为 \(x, y\) 均为正整数的解，\(\boldsymbol{0}\) 不是正整数。
整数解即为 \(x,y\) 均为整数的解。
\(x\) 的最小正整数值即所有 \(x\) 为正整数的整数解中 \(x\) 的最小值，\(y\) 同理。

输入格式

第一行一个正整数 \(T\)，代表数据组数。

接下来 \(T\) 行，每行三个由空格隔开的正整数 \(a, b, c\)。

输出格式

\(T\) 行。

若该行对应的询问无整数解，一个数字 \(-1\)。
若该行对应的询问有整数解但无正整数解，包含 \(2\) 个由空格隔开的数字，依次代表整数解中，\(x\) 的最小正整数值，\(y\) 的最小正整数值。
否则包含 \(5\) 个由空格隔开的数字，依次代表正整数解的数量，正整数解中，\(x\) 的最小值，\(y\) 的最小值，\(x\) 的最大值，\(y\) 的最大值。

实现

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
61
62
63
64
65
66

i64 ex_gcd(i64 u, i64 v, i64& x, i64& y) {
    if (!v) {
        x = 1, y = 0;
        return u;
    }

    i64 g = ex_gcd(v, u % v, x, y);
    i64 temp = x;
    x = y;
    y = temp - u / v * y;
    return g;
}

i64 a, b, c, g, x, y, ga, gb, maxx, maxy, minx, miny;
i64 t;
i64 k;

int main() {
    read(t);
    while (t--) {
        read(a, b, c);
        // if (a < b) std::swap(a, b);
        g = ex_gcd(a, b, x, y);
        x *= c / g, y *= c / g;
        if (c % g) {
            puts("-1");
        } else {
            ga = a / g;
            gb = b / g;

            /*
            此处先把 x 的最小正整数值求出来，容易想到 x 最小时 y 最大
            x > 1 时，直接往小取就行
            x <= 1 时，求 1 和 x 的差值然后把差值向上取整地消掉即可
            y 同理
            */
            if (x > 1) {
                k = (x - 1) / gb;
                minx = x - k * gb;
                maxy = y + k * ga;
            } else {
                k = ceil((1.0 - x) / gb);
                minx = x + k * gb;
                maxy = y - k * ga;
            }
            if (y > 1) {
                k = (y - 1) / ga;
                miny = y - k * ga;
                maxx = x + k * gb;
            } else {
                k = ceil((1.0 - y) / ga);
                miny = y + k * ga;
                maxx = x - k * gb;
            }

            // 如果 x, y 的最大值不是正整数，那么无正整数解，最小正整数 x, y 就是上面所求
            if (maxy <= 0 || maxx <= 0) {
                write(minx, ' ', miny, '\n');
            } else {
                // 此处算个数的时候需要注意要算自身，所以 + 1
                write((i64)ceil(maxy - 1.0) / ga + 1, ' ', minx, ' ', miny, ' ', maxx, ' ', maxy, '\n');
            }
        }
    }
    return 0;
}