확장 유클리드 알고리즘

?

ax+by=gcd(a, b)의 정수 해를 구하기 위해서 고안된 알고리즘!

설명

• a=0 인 경우에는 by=b, y=1 : (x, y)=(0,1)
• b=0인 경우에는 ax=a, x=1: (x, y)=(1,0)
• 종료 조건은 위와 같이 표현할 수 있음!

• 위처럼 유클리드 호제법과 비슷한 방식으로 처리가능하다.

using ll = long long;

tuple<ll, ll, ll> egcd(ll a, ll b) {
    if (b == 0) return {1, 0, a};
    auto [x1, y1, g] = egcd(b, a % b);
    return {y1, x1 - (a / b) * y1, g};
}