扩展欧几里得算法java代码

扩展欧几里得算法是一种用于求解两个整数最大公约数及其贝祖等式（ax + by = gcd(a, b)）的算法。下面是一个简单的Java代码实现：

public class ExtendedEuclideanAlgorithm {
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static int[] extendedGCD(int a, int b) {
        int x = 0, y = 0;
        int gcdValue = gcd(Math.abs(a), Math.abs(b));
        if (a < 0) {
            x = -gcdValue / a;
        } else {
            x = gcdValue / a;
        }
        if (b < 0) {
            y = -gcdValue / b;
        } else {
            y = gcdValue / b;
        }
        return new int[]{x, y, gcdValue};
    }

    public static void main(String[] args) {
        int a = 78, b = 46;
        int[] result = extendedGCD(a, b);
        System.out.println("gcd of " + a + " and " + b + " is: " + result[2]);
        System.out.println("Solution to Bezout's identity: " + result[0] + " * a + " + result[1] + " * b = " + result[2]);
    }
}

在这个例子中，`gcd()`函数计算两个数的最大公约数，而`extendedGCD()`函数则返回最大公约数以及一组满足贝祖等式的系数(x和y)。在`main()`方法中，我们给出了一个具体的实例并打印出结果。