首先有gcd(a,b)==gcd(b,a%b)这个复杂度最差也是log2的
因为大数对小数取余的时候 这个小数如果是比大数的一半大 那么取余完会比大数的一半大，如果小数比大数的一半小 那么取余完还是会比大数的一半大，所以最差也是log2的。因为大数对小数取
阅读背景：
拓展欧几里得理论基础（含一定证明）
来源：互联网
分享到：
