[백준] 12925. Numbers

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

문제 요약

• https://www.acmicpc.net/problem/12728
• 구글 코드잼에 나왔던 문제이고, 풀이도 있음

접근법

• 다시 풀어도 아이디어 도출이 어려웠음
• ${a = 3 + \sqrt{5}, b = 3 - \sqrt{5}}$
• 곱하면 4, 더하면 6 ==> 첫번째 걸림돌
• ${b^n < 1 (\because b <1)}$
• 그리고 나서 진행이 안됨! ==> 두번째 걸림돌
• ${a^2 + b^2 = (a + b) * (a + b)}$
• ${a^3 + b^3 = (a^2 + b^2) * (a + b) - a^2b - ab^2}$
• ${a^n + b^n = (a^{n-1} + b^{n-1}) * (a + b) - a^{n-1}b - ab^{n-1} }$
  ${= (a^{n-1} + b^{n-1}) * (a + b) - ab(a^{n-2}+b^{n-2})}$
  ${= 6(a^{n-1} + b^{n-1}) - 4(a^{n-2}+b^{n-2})}$
• ${a^n + b^n을 크게 묶어서 A_n으로 두면}$
• ${A_n = 6A_{n -1} - 4A_{n- 2}}$ ==> 행렬로 연산 가능
• 그런데 정수는 어떻게 구하나?? ${b^n < 1}$ 을 이용하면 될 것 같은데..
• ${A_n}$ 정수.xxxxxxxx 형태이면 빼기가 애매하다. ==> 세번째 걸림돌
• 그런데, ${A_1 = 6, A_2 = 28}$
• 즉 ${A_n}$은 정수가 된다는 이야기
• 결과적으로 ${A_n = 정수 = a^n + b^n}$
• ${a^n = 정수 - b^n = (정수-1).???????}$
• 그래서 구하고자 하는 값이 (정수-1)이 됨