题解 P2152 【[SDOI2009]SuperGCD】

Log_x · 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 的最大公约数。