◎学完你会
- 用辗转相除法求最大公约数 gcd，会用
__gcd(a,b)；
- 会用 lcm = a / gcd * b 求最小公倍数，并懂先除后乘防溢出；
- 会做约分、判断互质，理解裴蜀定理的直觉。
1动一动：辗转相除求 gcd(56,42)
规则：gcd(a,b) = gcd(b, a%b)，反复取余直到余数为 0，最后一步的除数就是最大公约数。
点「走一步」看每一步的被除数 / 除数 / 余数：
开始：gcd(56, 42)。56 % 42 = ?
余数为 0 时停止，最后的除数就是 gcd。这里 gcd(56,42)=14。
2关键命令：gcd 与 lcm
// 手写辗转相除
int gcd(int a,int b){ return b==0 ? a : gcd(b,a%b); }
// C++17 直接可用
gcd = __gcd(a, b);
// 最小公倍数：先除后乘防溢出
lcm = a / __gcd(a,b) * b;
lcm 必须写成 a/gcd*b（先除后乘），不要写 a*b/gcd——a*b 可能溢出。
裴蜀定理直觉：存在整数 x,y 使 ax+by=gcd(a,b)，这是扩展欧几里得的来源。
⚠易错点
a*b/gcd 溢出：两个 int 相乘先溢出，再除也救不回，必须先除后乘。
忘了 0 的 gcd：gcd(0,b)=b，递归基要写 b==0。
判断互质：gcd(a,b)==1 才是互质，不是两者都是质数。
?跨学科：最大公因数 = 找"共同的最小单元"
两块 56cm 与 42cm 的木板，要裁成一样长的最大段，每段 14cm——就是 gcd。
分子分母同除以 gcd 的约分，是分数化简的地基。
乐高、节拍对齐、时钟周期同步，本质都是"找最大公共周期"。
✎练一练
用辗转相除法求 gcd(56,42)，最后一步余数变为 0 时，gcd 等于？
余数变 0 时，最后的除数（即上一次的余数 14）就是 gcd——选 B。
已知 gcd(a,b)=d，求 lcm 的
防溢出写法应是什么？
答案：lcm = a / d * b。先除以 d 把结果缩小到能安全乘 b 的范围内，再乘 b。若先写 a*b 可能连 int 都装不下，因此"先除后乘"是必守的约定。