C 语言第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。

完整程序

#include <stdio.h>

int main(void)
{
    int a, b;
    if (scanf("%d %d", &a, &b) != 2) {
        return 1;
    }

    int x = a, y = b;
    // 逐步展示欧几里得辗转相除过程：被除数 / 除数 = 商 ... 余数
    while (y) {
        printf("%d / %d = %d ... %d\n", x, y, x / y, x % y);
        int t = x % y;
        x = y;
        y = t;
    }

    printf("gcd = %d\n", x);
    return 0;
}

运行示例

输入：

48 18

输出：

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