非递归代码：

#include<iostream>
using namespace std;
void exgcd(int a,int b,int& temp1,int& temp2){
    int x1=1,x2=0,x3=a,y1=0,y2=1,y3=b,t1=0,t2=0,t3=0;
    while(1){
        if(y3==0){
        temp1=x3,temp2=0;
        return ;
    }
        if(y3==1){
        temp1=y1,temp2=y2;
        return ;
    }

        int q=x3/y3;
        t1=x1-q*y1;
        t2=x2-q*y2;
        t3=x3-q*y3;
        x1=y1,x2=y2,x3=y3;
        y1=t1,y2=t2,y3=t3;
        cout<<x1<<' '<<x2<<' '<<x3<<' '<<y1<<' '<<y2<<' '<<y3<<endl;
    }

}
int main(){
    int a,b,n;
    int temp1,temp2;
    cin>>n;
   while(n--){
       cin>>a>>b;
       exgcd(a,b,temp1,temp2);
       cout<<temp1<<' '<<temp2<<endl;
   }
}

非递归代码解析：

该非递归代码源自密码学课本附录的欧几里得算法处，但是该非递归代码只适用于a,b两个数互质的情况下，如果不互质
返回两者的最大公因数。如16,24返回8.
对于该非递归代码的推理可见3.15日相册。

两种递归代码：

代码1

#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    else{

        int d= exgcd(b,a%b,x,y);
        int t=y;                 //一定要注意这些式子可以手动推出并且是放在exgcd()的下边，用于回溯的计算式子
         y=x-a/b*y;
         x=t;
        return d;
    }
}
int main(){
    int n;
    cin>>n;
    int x,y,a,b;
    while(n--){
        cin>>a>>b;
        int c=exgcd(a,b,x,y);
        cout<<x<<' '<<y<<endl;
    }

    return 0;
}

代码2

#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    else{

        int d= exgcd(b,a%b,y,x);
         y=y-a/b*x;                //一定要注意这些式子可以手动推出并且是放在exgcd()的下边，用于回溯的计算式子
        return d;
    }
}
int main(){
    int n;
    cin>>n;
    int x,y,a,b;
    while(n--){
        cin>>a>>b;
        int c=exgcd(a,b,x,y);
        cout<<x<<' '<<y<<endl;
    }

    return 0;
}