题解 P2152 【[SDOI2009]SuperGCD】

楼上一群神犇……我就解释下原理吧 对于 $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](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$ 的最大公约数。