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'..
