B3634题解
云裳
·
·
题解
管理员注：
阅读本文章前，请先阅读 chwu 关于 B 题库的声明，并了解由于课程需要不展示代码。
如需系统学习相关知识点请报名【洛谷 - 基础算法计划】
点赞上文章即代表您已阅读并熟知其内容。
思路
求最大公约数可以用辗转相除法，这里给出证明。
$a$ 可以表示成 $a = k \times b + r$（ $a$ , $b $, $k$ , $r$ 皆为正整数）。
假设 $d$ 是 $a,b$ 的一个公约数，记作 $d
\mid a$ , $d\mid b$。
而 $r = a - k\times b$，两边同时除以 $d$ ，$r/d=a/d-k\times b/d$，由等式右边可知 $m=r/d$ 为整数，因此 $d\mid r$。
因此 $d$ 也是 $b ,a\bmod b$ 的公约数。
因 $(a,b)$ 和 $(b,a\bmod b)$ 的公约数相等，则其最大公约数也相等，得证。
附：老师一扶苏一的证明。
------------
求最小公倍数可以拿 $a \times b / \gcd(a,b) $。
这里也给出证明。（借老师 WYXKK 的证明）。
附：老师 yurzhang 的证明。
---------
感谢以上老师的证明。