扩展 Euclid 算法 Euclid 算法 辗转相除法 计算两个数最大公因数 \(\text{gcd}(a,\,b) = \text{gcd}(b,\,a\%b)\) exEuclid 算法 裴蜀定理:\(\forall a,\,b,\,\,\exists x,\,y, \,\,s.t. \,\,ax+by=\gcd(a,b)\) 利用扩展Euclid 算法可以算出\(x\) 和\(y\) \(b=0\) 的,公因数就是\(a\) \(b\not= 0\) 时,根据Euclid 算法,有\(\