51. Extended Euclidean Algorithm

확장 유클리드 호제법(확장 유클리드 알고리즘, Extended Euclidean Algorithm, EGCD)은 다음과 같은 식에서 정수 $a, b$가 주어졌을 때 식을 만족하는 정수 $x, y$를 구하는 알고리즘이다.

$$ax+by=\gcd(a,b)$$

확장 유클리드 호제법은 유클리드 호제법을 이용하여 $x$와 $y$를 구한다. 만약 $a$와 $b$를 각각 $b$, $a\,\bmod\,b$로 바꿨을 때 다음 식을 만족하게 하는 $x', y'$을 알고 있다면,

$$bx'+(a\,\bmod\,b)y'=\gcd(a,b)$$

$a\,\bmod\,b=a-b\lfloor a/b \rfloor$이므로 식을 다음과 같이 변환할 수 있다.

$$bx'+(a-b\lfloor a/b \rfloor)y'=\gcd(a,b)$$

$$ay'+b(x'-y'\lfloor a/b \rfloor)=\gcd(a,b)$$

이때 $y'$과 $x'-y'\lfloor a/b \rfloor$는 처음 식의 해 $x, y$가 될 수 있다. 또한 $b=0$일 경우 $\gcd(a,b)=a$이므로 $x=1, y=0$이 해가 될 수 있다.

구현은 다음과 같다.

tuple<int, int, int> egcd(int a, int b)
{
    if(b == 0)return make_tuple(1, 0, a);
    tuple<int, int, int> t = egcd(b, a % b);
    int x = get<0>(t), y = get<1>(t), g = get<2>(t);
    return make_tuple(y, x - a / b * y, g);
}

만약 최대공약수를 반환할 필요가 없다면 tuple 대신 pair를 써서 구현할 수 있다.

pair<int, int> egcd(int a, int b)
{
    if(b == 0)return {1, 0};
    pair<int, int> p = egcd(b, a % b);
    return {p.second, p.first - a / b * p.second};
}

 

[연습문제]

 

Codeup 1298. Ax + By = C (Large)

$C$가 $\gcd(A,B)$의 배수가 아닐 경우 Not Exist를 출력하고, 배수라면 확장 유클리드 호제법을 이용해서 해를 구하면 된다. 해의 범위에 대한 제한은 없지만 부호 있는 $8$바이트 정수 자료형으로 표현할 수 있는 값을 출력하면 된다고 간주하면 된다.

 

BOJ 21568. Ax+By=C (Unrated)

이건 언제쯤 채점이 가능할까?

 

BOJ 9267. A+B (Dimaond V)

$a=0$ 또는 $b=0$인 경우를 먼저 처리하고, 그렇지 않은 경우 확장 유클리드 호제법으로 $ax+by=s$를 만족하는 $x$와 $y$가 존재하는지 확인하는데, $x>0, y>0$이고 $\gcd(x,y)=1$이어야 한다.

 

→ solved.ac tag: extended_euclidean