自动搬运

查看原文

来自洛谷，原作者为

	Log_x **

搬运于2025-08-24 21:34:33，当前版本为作者最后更新于2017-07-10 21:32:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

楼上一群神犇……我就解释下原理吧

对于 $a,b$ 的 $GCD(a, b)$ 有：

[1]. 若 $a$ 为奇数，$b$ 为偶数，$GCD(a, b) = GCD(a, b / 2)$

表示 $b$ 存在2这个因子而 $a$ 不存在，则将 $b$ 除以2,，不考虑因子2；

[2]. 若 $a$ 为偶数，$b$ 为奇数，$GCD(a, b) = GCD(a / 2, b)$

表示 $a$ 存在2这个因子而 $b$ 不存在，则将 $a$ 除以2，不考虑因子2；

[3]. 若 $a$ 为偶数，$b$ 为偶数，$GCD(a, b) = 2GCD(a / 2, b / 2)$

表示 $a, b$ 都存在2这个因子，则 $GCD(a, b)$ 也存在因子2，则将当前答案乘以2，$a, b$ 都除以2；

[4]. 若 $a$ 为奇数，$b$ 为奇数，$GCD(a, b) = GCD(a - b, b) (a > b)$

即辗转相减法（更相减损术），实际上可以看做辗转相除法的变形（因为减到不能再减实际上就是取余）。

最后顺便附上辗转相除法的证明：

（摘自http://blog.sina.com.cn/s/blog_6938cd0501010pj1.html）

设两数为$a,b(a>b)$，求它们最大公约数的步骤如下：用 $b$ 除 $a$ ，得 $a = bq + r(0 \le r < b)$（ $q$ 是这个除法的商）。若 $r = 0$ ,则 $b$ 是$a$ 和 $b$ 的最大公约数。若 $r \ne 0$，则继续考虑。

首先，应该明白的一点是任何 $a$ 和 $b$ 的公约数都是 $r$ 的公约数。要想证明这一点，就要考虑把 $r$ 写成 $r = a - bq$。现在，如果 $a$ 和 $b$ 有一个公约数 $d$，而且设 $a = xd , b = yd$， 那么 $r = xd - ydq = (x - yq)d$。因为这个式子中，所有的数（包括 $x - yq$ )都为整数，所以 $r$ 可以被 $d$ 整除。

对于所有的 $d$ 的值，这都是正确的；所以 $a$ 和 $b$ 的最大公约数也是 $b$ 和 $r$ 的最大公约数。因此我们可以继续对 $b$ 和 $r$ 进行上述取余的运算。这个过程在有限的重复后，可以最终得到 $r = 0$ 的结果，我们也就得到了 $a$ 和 $b$ 的最大公约数。