51. Extended Euclidean Algorithm
확장 유클리드 호제법(확장 유클리드 알고리즘, Extended Euclidean Algorithm)은 다음과 같은 식에서 정수 $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'..
