[16140] 정수론과 응용

가우시안 수 두 개 주고 GCD를 찾으라는 문제다.

 

3개의 subtask로 나누어져 있는데, 첫 번째는 새로운 차원을 사용하지 않는 정수 GCD, 두 번째는 아마도 좀 나이브하게 찾는(아니면 arctan 같은 걸 쓴다거나... 우웩.) 방식을 노린 것 같고, 마지막 subtask까지 전부 맞으려면 그보다는 좀 더 머리를 쓰는 방식을 요구하는 것으로 보인다.

 

우선 이 '가우시안 수' 라는 녀석을 살펴보자. 사실 그냥 복소수다. 이 가우시안 수 간의 곱셈은 다음과 같이 표현됨을 우리는 잘 안다.

두 복소수 $n = a + bi, m = c + di$에 대하여, $n \cdot m = (ac-bd) + (ad + bc)i$.

 

가우시안 수의 나눗셈에 대해 생각해 보자. 일단 가우시안 수를 서로 나눌 수는 있다. 그 결괏값이 가우시안 수인지 보장이 안 될 뿐이지만... 근데 이건 정수도 똑같다. 정수를 정수로 나눌 수 있지만, 그 결과가 정수임은 보장이 안 된다. 그래서 우리는 이를 보장할 수 있는, 몫과 나머지에 대하여 생각할 수 있다.

 

정수의 나눗셈에서 그 몫과 나머지는 모두 정수이다. 그렇다면 가우시안 수의 나눗셈에서도 몫과 나머지라는 개념을 생각할 수 있겠느냐 하면 당연히 yes.

일단 나눗셈은 원래 하던 방식대로 한다.

$\displaystyle \frac{n}{m} = \frac{a+bi}{c+di} = \frac{(a+bi)(c-di)}{(c+di)(c-di)} = \frac{ac+bd+(bc-ad)i}{c^2+d^2}$

이제 문제는 $\displaystyle \frac{ac+bd}{c^2+d^2}, \frac{bc-ad}{c^2+d^2}$가 정수가 아닌 경우에 어떻게 해야 하느냐인데, 간단하게 해결할 수 있다. 정수부와 실수부 둘 다 가장 가까운 정수로 반올림하고, 나머지는 몫에 $m$을 다시 곱한 걸 $n$에서 빼 버리면 된다!

 

어... 이렇게 보면 곱셈 있고, 덧셈 항등원 역원 있고 교환법칙 되고... 가우시안 수는 환(Ring) 이었다! 짜잔~

그 중에서도 사실 가우시안 수는 유클리드 환(Euclidean Ring) 이라는 것인데, 그냥 나눗셈 잘 되느냐 하는 조건만 더 붙은 거다. (나눗셈 정리랑 비슷한 거) 아마 이 가우시안 수의 나눗셈에서 몫과 나머지의 존재성과 유일성을 밝혀야 할 것 같은데, 여기서는 다루지 않겠다. ㅎㅎ;

 

미리 알고 있던 내용이라도 좋고 아니면 그냥 수 갖고 장난질 좀 쳐볼 수 있지 않을까? 싶어서 든 생각이라도 좋다. 어찌됐든 이런 꼴이면 유클리드 호제법, 그러니까 우리가 정수에서 GCD 구한다고 열심히 쓰던 바로 그 알고리즘을 갖다 쓸 수 있다. 그러면 풀린다.

 

이제 그냥 답을 딱 구해 놓고서 제출하기 전에 생각해야 할 게 있다. 다른 값들인데, 일단 호제법을 써서 한 개의 가우시안 수 $n$을 구했다고 생각해 보자. 그럼 $ni$는? $-n$은? $-ni$는 어떨까?

$24$와 $18$의 gcd가 $6$뿐 아니라 $-6$일 수도 있다는 힌트의 내용을 잘 생각해 보면...

16140번: 정수론과 응용