이 문제는 이런 식으로 풀 수 없습니다. 시간 복잡도가 O(n)인데,

n이 10억보다 훨씬 크기 때문에 절대 불가능이라고 생각하면 됩니다.

힌트-이 문제는 O(log n)에 푸는 것이 일반적입니다.

힌트-점화식을 빠르게 푸는 것은 00의 곱셈으로 가능합니다. 00까지 알고 싶다면...다시 댓글 달아주세요. 근데 직접 공부하는 것을 추천합니다.

🤔혹시 피사노 주기를 사용하는 것인가요? 제가 아는 선에서는 그것밖에 떠오르지 않네요. 알려주실 수 있을까요???

찾아보니 주기가 고정이네요. 그 방법도 가능할 것 같습니다.(저 댓글 달 때 주기가 있지만 길 것 같아서 그냥 안 적었는데 가능할 것 같네요.)

아무튼 제가 원래 의도한 방식은 행렬 곱셈입니다.

Fn=Fn-1 + Fn-2인데

trans(Fn,Fn-1)=trans((1,1),(1,0))*trans(Fn-1,Fn-2)가 됩니다.(행렬 쓰려니 힘드네요. trans는 여기서는 그냥 가로로 된 걸 세로로 바꿔준다고 생각하시면 됩니다.)

그럼 이걸 반복하면 trans(Fn, Fn-1)=trans((1,1),(1,0))^(n-1)*trans(F1,F0)이 되고, 행렬의 n-1승을 구해야 하는데, 이건 a^b를 빠르게 구하기 위해 O(logn)만에 구하는 방법을 똑같이 이용하면 됩니다.

-------------------

피보나치 4 문제 보니 이 문제는 피사노 주기로 푸는게 맞네요. 죄송합니다.

행렬식을 사용하는 방법이 있었군요. 감사합니다!