自动搬运

查看原文

来自洛谷，原作者为

	云裳 RP++

搬运于2025-08-24 21:14:04，当前版本为作者最后更新于2022-06-13 20:56:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

管理员注：

阅读本文章前，请先阅读 chwu 关于 B 题库的声明，并了解由于课程需要不展示代码。

如需系统学习相关知识点请报名【洛谷 - 基础算法计划】

点赞上文章即代表您已阅读并熟知其内容。

思路

求最大公约数可以用辗转相除法，这里给出证明。

$\gcd(a,b) = \gcd( b ,a\bmod b)$（不妨设 $a>b$ 且 $r=a \bmod b$, $r$ 不为 $0$ ）

$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 的证明。

感谢以上老师的证明。