当前位置：首页 > article >正文

C. Line: 用扩展欧几里得算法求解整数解

article 2025/1/6 18:28:37

一、题目背景

在平面上，一条直线可以用以下方程描述：

Ax+By+C=0Ax + By + C = 0

其中，系数 A,B,CA, B, C 和点的坐标 x,yx, y 均为整数。需要找到一个满足上述方程的点，使得其坐标 x,yx, y 都是整数。如果不存在这样的点，则输出 -1。

输入格式

单行包含三个整数 A,B,CA, B, C，满足： −2×109≤A,B,C≤2×109-2 \times 10^9 \leq A, B, C \leq 2 \times 10^9
保证 A2+B2>0A^2 + B^2 > 0，即 AA 和 BB 不会同时为 0。

输出格式

如果存在满足条件的点，则输出其坐标 x,yx, y（整数解）。
如果不存在满足条件的点，则输出 -1。

样例输入与输出

输入

2 5 3

输出

6 -3

输入

1 2 3

输出

-1

二、题目分析

本题的核心问题是如何找到整数解 (x,y)(x, y)，使其满足直线方程 Ax+By+C=0Ax + By + C = 0。考虑到 A,B,CA, B, C 的取值范围较大，且输入输出都要求整数，我们需要一个高效的算法来处理。

1. 方程化简

我们可以将方程 Ax+By+C=0Ax + By + C = 0 化简为：

Ax+By=−CAx + By = -C

令 D=−CD = -C，则问题转化为：

Ax+By=DAx + By = D

此时，我们需要通过数学方法找到整数解 x,yx, y。

2. 扩展欧几里得算法

扩展欧几里得算法是求解线性不定方程 Ax+By=gcd(A,B)Ax + By = gcd(A, B) 的经典方法。其核心思想是通过递归的方式，逆向构造出满足方程的整数解 x,yx, y。

2.1 标准欧几里得算法

欧几里得算法通过不断取余数，递归计算 AA 和 BB 的最大公约数（GCD）：

gcd(A,B)=gcd(B,A%B)gcd(A, B) = gcd(B, A \% B)

2.2 扩展欧几里得算法

扩展欧几里得算法在计算 GCD 的同时，还会计算出整数系数 x,yx, y，使得：

Ax+By=gcd(A,B)Ax + By = gcd(A, B)

具体实现为：

当 B=0B = 0 时，令 x=1,y=0x = 1, y = 0，此时 gcd(A,B)=Agcd(A, B) = A；
否则，递归调用扩展欧几里得算法，计算： gcd(B,A%B)=Bx′+(A%B)y′gcd(B, A \% B) = Bx' + (A \% B)y' 通过公式展开，得到： x=y′,y=x′−(A//B)y′x = y', \quad y = x' - (A // B)y'

2.3 特殊处理

扩展欧几里得算法只能保证解 x,yx, y 满足 Ax+By=gcd(A,B)Ax + By = gcd(A, B)。对于本题而言，如果 D%gcd(A,B)≠0D \% gcd(A, B) \neq 0，则方程无解，直接输出 -1。

三、解题思路

通过扩展欧几里得算法求解本题的具体步骤如下：

1. 判断方程是否有解

通过扩展欧几里得算法，计算 gcd(A,B)gcd(A, B)。如果 D%gcd(A,B)≠0D \% gcd(A, B) \neq 0，则方程无解。

2. 求初始解

如果 D%gcd(A,B)=0D \% gcd(A, B) = 0，则将方程两边同时除以 gcd(A,B)gcd(A, B)，化简为：

Agx+Bgy=Dg\frac{A}{g}x + \frac{B}{g}y = \frac{D}{g}

其中 g=gcd(A,B)g = gcd(A, B)。使用扩展欧几里得算法，求得初始解 x0,y0x_0, y_0 满足：

Agx0+Bgy0=1\frac{A}{g}x_0 + \frac{B}{g}y_0 = 1

则解的形式为：

x=x0⋅Dg,y=y0⋅Dgx = x_0 \cdot \frac{D}{g}, \quad y = y_0 \cdot \frac{D}{g}

3. 调整解的符号

由于题目要求输出的整数解是满足方程的点，需对解的符号进行调整以满足约束。

四、Python代码实现

以下是完整的Python代码：

def extended_gcd(a, b):
    """扩展欧几里得算法，返回 gcd(a, b) 及满足 Bézout 等式的系数 x, y"""
    if b == 0:
        return a, 1, 0
    gcd, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return gcd, x, y


def solve_line_equation(a, b, c):
    """
    求解 Ax + By + C = 0 的整数解
    :param a: 方程中的系数 A
    :param b: 方程中的系数 B
    :param c: 方程中的系数 C
    :return: 一个整数解 (x, y) 或 -1（无解）
    """
    # 转化为 Ax + By = -C
    d = -c
    gcd, x, y = extended_gcd(a, b)
    
    # 判断是否有解
    if d % gcd != 0:
        return -1
    
    # 计算整数解
    x = x * (d // gcd)
    y = y * (d // gcd)
    return x, y


def main():
    # 输入三个整数 A, B, C
    a, b, c = map(int, input("请输入 A, B, C（以空格分隔）: ").split())
    
    # 求解方程
    result = solve_line_equation(a, b, c)
    
    # 输出结果
    if result == -1:
        print("-1")
    else:
        print(f"{result[0]} {result[1]}")


if __name__ == "__main__":
    main()