extgcd_1.cpp

#include<bits/stdc++.h>
using namespace std;

int extgcd(int a,int b,int &x,int &y){
	if(b==0){ //a*1+b*0=a　なので！
    	x=1;
      	y=0;
      	return a;
    }
  
  
  	int g=extgcd(b,a%b,x,y);
  	int next_x,next_y;
  	next_x=y;
  	next_y=x-(a/b)*y;
  
  	x=next_x;
  	y=next_y;
  
  	return g;
}


int main(){
 	int a=12;
  	int b=18;
  
  	int x,y;
 	int g=extgcd(a,b,x,y);
  	cout<<g<<endl;   //6
  	cout<<x<<" "<<y<<endl; //-1 1
  	cout<<a*x+b*y<<endl;  //6
}

extgcd_2.cpp

int extgcd(int a,int b,int &x,int &y){
	if(b==0){ //a*1+b*0=a　なので！
    	x=1;
      	y=0;
      	return a;
    }
  
  
 int g=extgcd(b,a%b,x,y);
    swap(x,y);
  	int next_x,next_y;
  	next_x=x;
  	next_y=y-(a/b)*x;
  
  	x=next_x;
  	y=next_y;
  
  	return g;
}

extgcd_3.cpp

int extgcd(int a,int b,int &x,int &y){
	if(b==0){ //a*1+b*0=a　なので！
    	x=1;
      	y=0;
      	return a;
    }
  
  
  	int g=extgcd(b,a%b,x,y);
    swap(x,y);
  	//next_x=x;
  	//next_y=y-(a/b)*x;
    y-=(a/b)*x;
  	return g;
}

extgcd_4.cpp

int extgcd(int a,int b,int &x,int &y){
	if(b==0){ //a*1+b*0=a　なので！
    	x=1;
      	y=0;
      	return a;
    }
  
    //int g=extgcd(b,a%b,x,y);
    //swap(x,y);	
    int g=extgcd(b,a%b,y,x);
    
  	//next_x=x;
  	//next_y=y-(a/b)*x;
    y-=(a/b)*x;
  	return g;
}