転がり相除去法(ユークリッドアルゴリズム)と拡張ユークリッドアルゴリズム

転がり相除去法(ユークリッドアルゴリズム)と拡張ユークリッドアルゴリズム
転がり相除去法:転がり相除去法は2つの自然数の最大公約数(gcd)を求める方法であり、ユークリッドアルゴリズムとも呼ばれる.
例えば、求める(319377):
⑪319÷377=0(残り319)
∴(319,377)=(377,319);
⑪377÷319=1(残り58)
∴(377,319)=(319,58);
⑪319÷58=5(残り29)
∴ (319,58)=(58,29);
⑪58÷29=2(残り0)
∴ (58,29)= 29;
∴ (319,377)=29.
したがって,(a,b)の最大公約数を要求すると=(a,b)は(b,a%b)==に相当する.
転がり相除算法でいくつかの数の最大公約数を求めると,その中の任意の2つの数の最大公約数を先に求めることができ,この最大公約数と3番目の数の最大公約数を順次求め,最後の数まで求めることができる.最後に得られた最大公約数は、これらのすべての数の最大公約数です.

#include 

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

int main() {
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d", func(a,b));
}

拡張ユークリッドアルゴリズム
要求ax+by=1の解注意:a,b,x,yはすべて整数である
aとbの最大公約数が1に等しいときx,yはやっと解があることが分かった.
導出プロセス:gcd(a,b)=cかつc!=1 a=nc,b=mcでax+by=1がc(xn+ym)=1になるとxとyは解けないことがわかる
拡張ユークリッドアルゴリズム:ax+by=gcd(a,b)(gcd(a,b)がaとbの最大公約数である場合)任意のa,bを入力してx,yの値(a,b,x,yはすべて整数)を求める

#include
int ex_gcd(int a,int b,int &x, int &y) {
    if(!b){
        x = 1,y = 0;
        return a;
    }
    int xx,yy, ret = ex_gcd(b, a % b,xx, yy);
    x = yy;                               
    y = xx - a / b *yy;
    return ret;
}

int main() {
    int a, b, x, y;
    while (~scanf("%d%d",&a, &b)) {
        ex_gcd(a,b,x,y);
        printf("%d * %d + %d * %d = %d
",a,x,b,y,a * x +b * y);
    }
    
}

拡張ユークリッドアルゴリズムは主に再帰アルゴリズムを用い,再帰アルゴリズムではプログラム終了の条件,本層と次層の関係式,およびどの層の値を返すかを考慮する.
以下を参照してください.
https://blog.csdn.net/destiny1507/article/details/81750874
https://blog.csdn.net/qmdweb/article/details/80537602