백엔드 개발자

유클리드 호제법 a 와 b의 최대공약수는 b와 (a%b)의 최대 공약수와 같다 (a>b 일 경우) ex) 12 와 8의 최대 공약수는 12나누기 8의 나머지 값인 4와 8의 최대 공약수와 같다. gcd(12,8) == gcd(8,12 mod 8 ) 확장 유클리드 호제법 전혀 어렵지 않다. 유클리드 호제법과 유사하다. 선형 방정식 ax + by = gcd(a,b) 일 경우 x와 y의 값을 구할 수 있다. 유클리드 호제법을 적용한다. 위 식에서 gcd(a,b) == gcd(b, a%b) == gcd(a%b , b%(a%b)) .......... 이런식으로 유클리드 호제법을 적용해주게 된다. 어떻게 예를 들어 a = 300, b = 200 일 때, 300x + 200y = gcd(300, 200) 이라 하면 ..