Java最大公约数算法：扩展欧几里得算法及其应用场景

# 1. 最大公约数算法概述

最大公约数（GCD）算法用于求取两个或多个整数的最大公约数。最大公约数是指这些整数的公约数中最大的一个。GCD算法在数学和计算机科学中有着广泛的应用，例如在密码学、数据结构和算法优化中。

最常用的GCD算法之一是辗转相除法。该算法基于以下原理：两个整数的最大公约数等于其中较小整数与较大整数的余数的最大公约数。因此，辗转相除法通过不断求取余数来逐步缩小求解范围，直到求得最大公约数。

# 2. 扩展欧几里得算法**

**2.1 算法原理**

扩展欧几里得算法是一种用于求解不定方程组的算法，它在求解线性同余方程组、模逆元和快速幂计算等问题中有着广泛的应用。

该算法基于欧几里得算法，其核心思想是利用辗转相除法求出两个整数的最大公约数（GCD），并同时求出两个整数的线性组合，使得其等于最大公约数。

具体来说，对于给定的两个整数 a 和 b，扩展欧几里得算法的步骤如下：

1. **初始化：**令 r0 = a，r1 = b，s0 = 1，s1 = 0，t0 = 0，t1 = 1。
2. **辗转相除：**不断计算 r2 = r0 % r1，并更新 s2 = s0 - (r0 // r1) * s1 和 t2 = t0 - (r0 // r1) * t1。
3. **更新：**将 r0、s0、t0 分别更新为 r1、s1、t1，将 r1、s1、t1 分别更新为 r2、s2、t2。
4. **循环：**重复步骤 2 和 3，直到 r1 为 0。
5. **求解：**当 r1 为 0 时，r0 即为 a 和 b 的最大公约数，s0 和 t0 分别为满足方程 ax + by = GCD(a, b) 的两个整数解。

**2.2 算法实现**

以下是用 Java 实现的扩展欧几里得算法：

public static int[] extendedGCD(int a, int b) {
    int[] s = new int[3]; // 存储系数
    if (b == 0) {
        s[0] = 1;
        s[1] = 0;
        s[2] = a;
        return s;
    }
    int[] r = extendedGCD(b, a % b);
    s[0] = r[1];
    s[1] = r[0] - (a / b) * r[1];
    s[2] = r[2];
    return s;
}

**参数说明：**

* a：第一个整数
* b：第二个整数

**代码逻辑：**

* 如果 b 为 0，则 a 和 b 的最大公约数为 a，系数 s0 为 1，s1 为 0，返回结果。
* 否则，递归调用 extendedGCD(b, a % b) 求解 b 和 a % b 的最大公约数和系数。
* 将递归返回的系数 s0 和 s1 更新为 s1 和 s0 - (a / b) * s1。
* 返回最大公约数和更新后的系数。

**2.3 算法复杂度**

扩展欧几里得算法的时间复杂度为 O(log(min(a, b))，其中 min(a, b) 表示 a 和 b 中较小的一个。这是因为算法的每个步骤都将 r1 缩小到 r1 的一半，因此算法最多执行 log(min(a, b)) 次迭代。

# 3.1 线性同余方程组求解

#### 线性同余方程组定义

线性同余方程组由一组关于未知数的线性同余方程组成，形式如下：

x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
x ≡ an (mod mn)

其中：

* x 是未知数
* ai 是常数
* mi 是模数

#### 扩展欧几里得算法求解

扩展欧几里得算法可以用来求解线性同余方程组。具体步骤如下：

1. 将方程组转化为一个扩展欧几里得方程：

Bezout(m1, m2, s, t) = gcd(m1, m2)

其中：

* Bezout() 函数计算扩展欧几里得算法的系数 s 和 t
* gcd() 函数计算最大公约数

2. 求解每个方程：

x ≡ a1 * s1 (mod m1)
x ≡ a2 * s2 (mod m2)
x ≡ an * sn (mod mn)

其中：

* si 是扩展欧几里得方程的系数
* s1 = s / gcd(m1, m2)
* s2 = t / gcd(m1, m2)
* ...
* sn = t / gcd(mn-1, mn)

3. 合并解：

x ≡ (a1 * s1 + a2 * s2 + ... + an * sn) (mod m)

其中：

* m = m1 * m2 * ... * mn

#### 代码实现

import java.util.Scanner;

public class LinearCongruence {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入方程组数量
        int n = scanner.nextIn