java的拓展欧几里得

拓展欧几里得算法是欧几里得算法的扩展，除了计算两个整数的最大公约数，还能找到整数x和y，使得ax + by = gcd(a, b)。该算法的原理是应用反复带余除法来实现。以下是一个Java实现的例子:

import java.util.Scanner;

public class ExtendedEuclideanAlgorithm {
    public static void main(String[] args) {
        int a, b, c, d, s = 0, t = 0;
        /*其中a是被除数 b是除数 c是商 d是余数*/
        d = 1;
        int s1 = 1, s2 = 0, t1 = 0, t2 = 1;
        Scanner sc = new Scanner(System.in);
        a = sc.nextInt();
        b = sc.nextInt();
        int aa = a;
        int bb = b;
        while (d != 0) {
            c = a / b;
            d = a % b;
            s = s1 - c * s2;
            t = t1 - c * t2;
            if (d != 0) {
                a = b;
                b = d;
                s1 = s2;
                s2 = s;
                t1 = t2;
                t2 = t;
            }
        }
        System.out.println("两个整数的最大公因数为 " + b);
        System.out.println("输出 sa * tb = d 的形式如下：");        System.out.println("(" + s2 + ") * " + aa + " + (" + t2 + ") * " + bb + " = " + b);
    }
}