Java第30题：辗转相除法手写过程逐步打印

题目

从标准输入读入两个正整数 a 和 b，使用辗转相除法求最大公约数，并在控制台逐步打印出每一步的除法带余运算过程。

输入格式：一行输入两个正整数 a 和 b，以空格分隔。

输出格式：逐步打印每轮的 被除数 = 除数 * 商 + 余数，最后输出最大公约数结果。

数据范围与约定：1 ≤ a, b ≤ 10⁹。

思路与算法

1. 辗转相除过程跟踪
每轮计算中，商为 q = a / b，余数为 r = a % b。输出格式化字符串 %d = %d * %d + %d。

2. 迭代推进
打印完成后更新 a = b; b = r;，直到余数 r == 0 终止，此时的被除数即最终 GCD。

完整程序

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        int x = a, y = b;
        // 逐步展示欧几里得辗转相除过程：被除数 / 除数 = 商 ... 余数
        while (y != 0) {
            System.out.println(x + " / " + y + " = " + (x / y) + " ... " + (x % y));
            int t = x % y;
            x = y;
            y = t;
        }

        System.out.println("gcd = " + x);
    }
}

运行示例

输入：

48 18

输出：

48 / 18 = 2 ... 12
18 / 12 = 1 ... 6
12 / 6 = 2 ... 0
gcd = 6