[일반] [컴퓨터 문제] 정수론 질문

[익명(112.186)]

이 문제가 대충 유클리드 호제법의 성질을 이용해서 푸는건 알겠는데 문제는 해설을 찾아보니

a, |a - b|로 바꾸는 경우랑 b, |a - b|로 바꾸는 경우를 전부 고려하지 않고 하나만 봐도 되는 것 같은데 왜 그런지 의문입니다.

[익명(77.103)]

a>b에 대해서 {a, a-b}만 고려하면 됨. 왜냐하면 {a, a-b}에 대해서 똑같은 연산을 수행하면 {b, a-b}를 어차피 얻기 때문.

[익명(106.101)]

확장 유클리드 알고리즘