[12728] n제곱 계산

%2021. 11. 20. 04:01에 작성된 글입니다%

https://www.acmicpc.net/problem/12728

12728번: n제곱 계산

 

깡계산은 어림도 없다.

일단 \(3+\sqrt 5\)의 모양을 보아 하니 \(3-\sqrt 5\)도 같이 딸려나와야 뭐가 될 것 같아 보인다. 이차방정식 켤레근? 뭐 이런 느낌으로 탁 튀어나올 수 있기야 있겠다만서도 사실 처음부터 이걸 잡고 가야겠다는 생각이 바로 드는 건 어렵겠다...
아니면 내가 알지 못하는 어떤 지식에 의해서 \(3-\sqrt 5\)의 도입이 필연적으로, 혹은 너무나도 직관적으로 보일 수도 있을...까? 모르겠네

일단 \(n\)승을 해야 하는 문제고 \(n\)의 범위가 20억까지니까 \(O(N)\)보다 작은 알고리즘을 갖고 와서 해결을 봐야 한다.
단순 계산은 당연히 안 되니까 어떤 형태로 수를 분리를 하고, \(n\)승과 \(2n\)승 / \(n\)승과 \(n+1\)승 간의 관계식을 밝혀 내면 되리라!

문제를 풀고 나서 보니 정해는 행렬을 사용하던데, 여기서는 내가 행렬을 다루는 데에 익숙하지 않은 탓에 튜플 점화식(?)으로 설명한다.

우선 좀 간단하게 보기 위해서 \(a\)와 \(b\)를 다음과 같이 정의하자.
\(a=3+\sqrt{5},\ b=3-\sqrt{5}\)​
한 정수와 \(\sqrt 5\)의 배수의 합으로 이루어진 실수 \(r\)에 대하여 다음과 같은 표기를 정하자.
\(r=n+m\sqrt 5=\left(n,\ m\right)\ \left(n,m\in\mathbb{Z}\right)\)​
이제 \(a^n\)과 \(a^{2n}\), \(a^{n+1}\) 사이의 관계를 밝혀내자.
\(a^n=\left(x,\ y\right)=x+y\sqrt{5}\ \left(x,y\in\mathbb{Z}\right)\)​
\(\Rightarrow \ a^{2n}=x^2+5y^2+2xy\sqrt{5}=\left(x^2+5y^2,\ 2xy\right),\)​
\(a^{n+1}=\left(x+y\sqrt{5}\right)\left(3+\sqrt{5}\right)=3x+5y+\left(x+3y\right)\sqrt{5}\)​
\(=\left(3x+5y,\ x+3y\right)\)​
이제 다 되었는데 주목할 것이 하나 있다. \(a^n\)이 \((x, y)\)라면 \(b^n\)은 어떻게 표현될까?
바로 \((x, -y)\)이다. \(\sqrt 5\)가 짝수번 곱해지는 경우에는 전부 정수로 넘어가버리고 양수가 되는 반면 홀수번 곱해지는 경우에는 부호가 반전된 채로 \(\sqrt 5\)가 남기 때문에 당연한 결과이다.

그러면 \(a^n+b^n\)은 \((2x, 0)\)이 되고, \(b^n\)은 \(n\)의 입력 범위인 \(2\)~\(2\cdot 10^9\)에서 항상 \(1\)보다 작음을 감안하면 \(\lfloor a^n\rfloor\)은 \(2x\)보다 작은 정수 중 가장 큰 값, 즉 \(2x-1\)이 될 것이다. 이제 저 튜플에 간단하게 표현한 대로 분할정복 함수를 잘 구현하면
 끝이다.

\(x,y\) 모두 자연수이기 때문에 계산 도중에\(\mod 1000\)을 계속 때려도 아무런 문제 없이 답이 튀어나온다.