辗转相除法与欧几里得算法

常规的辗转相除算法用于计算两个数的最大公约数

 int gcd(int a,int b)

    
 {
    
   if(b==0) return a;
    
   return gcd(b,a%b);
    
 }
    
    
    
    

2.【2.扩展欧几里得算法

寻找整数x和y满足ax+by=1的条件

可以观察到，当gcd(a,b)不等于1时，该方程无解。

而当gcd(a,b)等于1时，则可以通过扩展欧几里得算法进行求解：即ax+by=gcd(a,b)，

定义函数int extgcd(int a ,int b,int &x,int &y)，用于求解上述方程，其返回值为gcd(a,b)。与普通gcd算法类似，extgcd同样可以采用递归方式实现。

在欧几里得算法中，终止条件为a= gcd且b=0。这种状态是否能够为我们求解x和y提供某种思路？因为在这一状态下，只要a的系数为1，而b的系数无论为何值（由于任何数乘以0都为0），此时我们都可以得到：a1 + b0 = gcd。

当然这只是最终状态的一种情况，那么我们是否可以从这一最终状态逆向推导回初始状态呢？

假设现在需要计算a和b的最大公约数，并找出满足ax + by = gcd的一组x和y。同时我们已经得到了下一个状态的结果：即计算了b与a%b的最大公约数，