题解 P2152 【[SDOI2009]SuperGCD】

阮行止 · 2018-07-13 14:33:42 · 题解

辟谣

本题使用更相减损术可以通过，但是请注意：更相减损术的复杂度是O(n)，其中n为A,B中较大的那个一个。

我们给一个例子：A=10^{10000},B=1.此时更相减损术会挂掉。

更相减损术的原理是：\gcd(a,b)=\gcd(a,a-b).
辗转相除法的原理为GCD递归定理：\gcd(a,b)=\gcd(b,a\%b).

容易看出，两个定理是等价的。而辗转相除法由于以取模代替多次减法，复杂度为O(\log n).

这个复杂度有一个很美妙的证明。

• 情况一：a<b.此时GCD递归定理完成a,b的交换，转为情况二。
• 情况二：a\geqslant b.我们注意到：一个数模比自己小的数，至少减少一半。故a至少减少一半。

情况一的出现次数不会高于情况二的出现次数；而情况二的出现次数至多为O(\log n).自此完成复杂度证明。

事实上，辗转相除法面临的最坏情况是斐波那契数列的相邻两项。读者可以想一想这是为什么。

最后，请各位老老实实地写辗转相除法。除非数据有特殊性质，否则不要使用更相减损术来求gcd.