欧几里德算法扩展

扩展欧几里德算法是用来在已知a,b求解一组x，y，使它们满足贝祖等式:ax+by=gcd(a,b)=d(解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。扩展欧几里德算法是用来在已知a,b求解一组p，q使得p*a+q*b=Gcd(a,b)(解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。下面是一个使用C++的实现: