拡張ユークリッドアルゴリズムと実現

整数a,bの最大公約数を求めるために,ユークリッドアルゴリズム,すなわち転がり相除算法を用いた.
ユークリッドアルゴリズムC++実装コード:(a,bサイズ関係を決定する必要はない)

long long gcd(long long a,long long b){
    return b?gcd(b,a%b):a;
}

拡張ユークリッドアルゴリズム:aとbがすべて0でないと、gcd(a,b)=xa+ybとなるように整数xとyが存在する
証明:a>bを仮定する
b=0の場合:gcd(a,b)=a、この場合x=1、y=0
ab!=0の場合:
x 1 a+y 1 b=gcd(a,b)
x2b + y2(a%b) = gcd(b,a%b)
gcd(a,b)==gcd(b,a%b)
したがってx 1 a+y 1 b=x 2 b+y 2(a%b)=x 2 b+y 2(a-a/b*b)=y 2 a+x 2 b-y 2(a/b)*b
従ってx 1=y 2,y 1=x 2−(a/b)y 2
これによりx 2,y 2に基づいてx 1,y 1の解を求めることができる.
拡張ユークリッドC++実装コード01:

long long Exgcd(long long a,long long b,long long& x,long long& y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    long long d=exgcd(b,a%b,x,y);
    long long tmp=x;
    x=y;
    y=tmp-a/b*y;
    return d;
}

拡張ユークリッドC++実装コード02:

#define ll long long
void Exgcd(ll a,ll b,ll& d,ll& x,ll& y){
    if(!b){ d=a;x=1;y=0;return ;}
    Exgcd(b,a%b,d,y,x);
    y -= a/b*x ;
    return ;
}