Fibonacci Representation

• 그리디하게, 만들려는 수에 가장 근접한 피보나치 수를 찾아서 포함시키는 방식으로 반복하면 찾을 수 있다.
  • f(n) 이하의 피보나치 수들만을 더해서 만들어진 수가 f(n+1)이상이라면, 이것을 f(n+1)을 포함하는 피보나치수의 합으로 바꿔 쓰는 것이 항상 가능하고, 이 경우에 더해지는 피보나치수의 갯수가 증가하지는 않는다.
  • Zeckendorf's_theorem도 참고하자.
• 만들려는 수에 가장 근접한 피보나치 수를 찾는 것은 몇가지 방법이 있는데.. 만들려는수가 x이고, F(m) <= n < F(m+1)인 F(m)과 F(m+1)을 구하는거라고 하자. 그러면 m은 O(logn)이다.
  • 그냥 전처리 없이 F(1),F(2),… 를 계속 만들어가면서 찾는다면 O(m)
  • F(i)을 모두 전처리해서 O(m)에 미리 구해놓고서, 이분탐색으로 찾는다면 O(logm)
  • 피보나치 수의 일반식 $F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor$ 을 역으로 써서 $n(F)=\left\lceil \log _{\varphi }\left(F\cdot {\sqrt {5}}-{\frac {1}{2}}\right)\right\rceil $으로 계산하는 방법
    • O(1)에 m을 구할수 있고.. F(i)을 모두 전처리해서 미리 구해놨다면 F(m)을 구하는 것까지도 O(1)이겠지만.. 계산도 복잡하고 실수오차도 있을거 같은 느낌..
  • 결국은 m자체가 별로 크지 않으니까 (n⇐4*10^17 문제조건에서 m은 100 이하이다) 가장 간단한 첫번째 방법으로 구현했다. 이 방식으로 m 개의 항을 구해도 O(m^2) = O(log^2(n))이다
• O(m^2)으로 풀고 나서, 다른 사람 답안을 보다가 훨씬 좋은 방법을 알게 되었다. n에 가장 근접한 피보나치 수 F(m)을 찾아서 빼 준다음에, n-F(m)에 가장 근접한 피보나치 수를 찾으려고 할때, 다시 F(0)부터 만들어나가며 찾을 필요가 없다. F(m-1)에서부터 아래로 내려오면서 찾으면 되고, 이런식으로 접근하면 피보나치수들을 다시 한번씩만 만들게 되면 끝나므로, 결국 O(m^2)이 아니라 O(m)에 해결 가능하다.
  • 실제 수행시간은 m이 작아서 시간차이는 하나도 안난다.

"""Solution code for "BOJ 8229. Fibonacci Representation".

- Problem link: https://www.acmicpc.net/problem/8229
- Solution link: http://www.teferi.net/ps/problems/boj/8229

Tags: [Greedy]
"""


def main():
    p = int(input())
    for _ in range(p):
        k = int(input())

        answer = 0
        while k:
            a, b = 1, 1
            while b <= k:
                a, b = b, a + b
            k = min(b - k, k - a)
            answer += 1

        print(answer)


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 8229. Fibonacci Representation".

- Problem link: https://www.acmicpc.net/problem/8229
- Solution link: http://www.teferi.net/ps/problems/boj/8229

Tags: [Greedy]
"""


def main():
    p = int(input())
    for _ in range(p):
        k = int(input())

        answer = 0
        a, b = 1, 1
        while b <= k:
            a, b = b, a + b
        while k:
            while a > k:
                a, b = b - a, a
            k = min(b - k, k - a)
            answer += 1

        print(answer)


if __name__ == '__main__':
    main()