ユークリッドアルゴリズムと拡張ユークリッドアルゴリズム(Gcd and Exgcd)

作用:最大公約数を求めるユークリッドアルゴリズムユークリッドアルゴリズムは転がり相除法とも呼ばれ、2つの整数a,bの最大公約数を計算するために使用される.その計算原理は以下の定理に依存する:証明過程:
定理:gcd(a,b)=gcd(b,a mod b)
証明:aはa=kb+rと表すことができ、r=a modbはdがa,bの公約数であると仮定し、d|a,d|bがあり、r=a−kbであるため、d|rはd(b,a modb)の公約数である
dが(b,a mod b)の公約数であると仮定するとd|b,d|rであるが、a=kb+rであるのでdも(a,b)の公約数である
従って(a,b)と(b,a mod b)の公約数は同じであり、その最大公約数も必然的に等しいので、転々とした相殺コードは以下の通りである.

int Gcd(int a, int b)
{
     
    if(b == 0)
        return a;
    return Gcd(b, a % b);
}
//    
int Gcd(int a, int b)
{
     
    while(b != 0)
    {
     
        int r = b;
        b = a % b;
        a = r;
    }
    return a;
}

拡張ユークリッド:作用:既知のa,bでpのセットを解き,qはp*a+q*b=Gcd(a,b)(解が必ず存在し,数論における相関定理に基づいて)である.拡張ユークリッドはモード線形方程式と方程式群を解くのによく用いられる.
ax+by=gcd(a,b)のような形の同余方程式を解くためのアルゴリズム

//    
int exGcd(int a, int b, int &x, int &y)
{
     
    if(b == 0)
    {
     
        x = 1;
        y = 0;
        return a;
    }
    int r = exGcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;

    return r;
}

あるいは

#include  
#include   
using namespace std;
int a,b,x,y;
void exgcd(int a,int b){
     
    if(b==0){
     
        x=1,y=0;
        return;
    }
    exgcd(b,a%b);
    int temp=x;
    x=y,y=temp-a/b*y;
    return;
}
int main(){
     
    cin>>a>>b;
    exgcd(a,b);
    //cout<
}

具体的な証明過程:証明過程の詳細はこの文章を参照してください.