====== 피보나치 수 (Fibonacci numbers) ======

  * [[https://www.acmicpc.net/blog/view/28|피보나치 수를 구하는 여러가지 방법]] 과 [[https://cp-algorithms.com/algebra/fibonacci-numbers.html]]를 참고
  * F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) 의 형태로 정의되는 수열. 초기 몇 항의 값은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 이다
  * 여러가지 DP 문제들의 답이 피보나치 수가 되는 경우도 많고, 또한 수열 자체에도 여러가지 성질들이 많아서 그것들에 관한 문제도 많이 나온다. [[wp>ko:피보나치 수]] 참고

===== n번째 피보나치 수를 구하기 =====
  * 비네의 공식(Binet's formula) 이라고 불리는 클로즈드 폼으로 된 일반항 공식이 있기는 하지만, 이 공식을 이용해서 계산하는 것은 실수오차때문에 사용하기 힘들다. 
  * 피보나치 수의 점화식도 [[ps:선형_점화식#상수계수의_선형_점화식_동차_선형_점화식|동차 선형 점화식]]이므로, 행렬의 거듭제곱을 이용해서 O(logn)에 푸는 것이 효율적인 방법이다.
  * 행렬 거듭제곱 형태를 좀 더 정리하면, 아래 점화식을 얻을 수 있고 이것을 이용해서 풀 수도 있다. 시간복잡도는 역시 O(logn)이지만, 계산이 살짝 더 최적화된다.
    * $$ F_{2k}=F_k(2F_{k+1}−F_k) \\
F_{2k+1} = F^2_{k+1} + F^2_{k} $$
      * 이 식은, 다음의 도가뉴 항등식(d'Ocagne's identity) 으로부터도 쉽게 유도된다
        * $ F_{m+n}=F_{m-1}F_{n}+F_{m}F_{n+1} $
    * 구현은 [[:ps:teflib:combinatorics#fibonacci|teflib.combinatorics.fibonacci]] 을 참고.  
  * 관련 문제
    * [[ps:problems:boj:11444]]
 
==== m=2^x*5^y 일때, F(n) % m 을 구하기 ==== 
  * 피사노 주기([[wk>pisano period]])를 이용하면 F(n) % mod 를 구하는 것을, mod에 대한 피사노 주기 π(mod)를 구한 다음에 F(n%π(mod))%mod 로 계산할 수 있다. 
  * 하지만, π(mod)를 구하는 것이 보통은 쉽지 않다. 그나마 쉽게 계산할수 있는 경우는 mod가 2^x*5^y 형태일때 이다
    * m,n이 서로소라면 π(mn) = LCM(π(m), π(n))
    * n = 2^k 라면 π(n) = 3n/2
    * n = 5^k 라면 π(n) = 4n
  * 이렇게 피사노 주기를 이용하면, n번째 피보나치수 대신에, n%π(mod) 번째 피보나치수를 구하면 되므로, 시간복잡도가 O(logn)에서 O(log(π(mod)))로 줄어들기는 한다. 하지만, 그냥 O(logn)으로 구하더라도 어지간히 큰 n에 대해서도 매우 빠르게 계산해주기 때문에 굳이 꼭 필요한 경우는 거의 없다.
  * 관련 문제
    * [[ps:problems:boj:2749]]

===== 관련된 성질 / 정리 =====
  * 피보나치 수열의 급수와 변형된 급수들은 대부분 더 큰 피보나치수를 이용해서 표현이 가능하다
    * k번 항까지의 합, 교대합, 홀수항의 합 등등은 다 피보나치 수로 변환되고, 따라서 O(logn)에 계산 가능하다
  * 피보나치 수들의 최대공약수도 피보나치수로 표현된다. 두 피보나치 수의 서로소 여부도 쉽게 알수 있다
  * 

==== 급수 공식 ====
  * [[https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98#%EA%B8%89%EC%88%98_%EA%B3%B5%EC%8B%9D|위키피디아]] 참고
  * 합: $ {\displaystyle \sum _{k=0}^{n}F_{k}=F_{n+2}-1} $
  * 교대합: $ {\displaystyle \sum _{k=0}^{n}(-1)^{k+1}F_{k}=(-1)^{n+1}F_{n-1}+1} $
  * 제곱합: $ {\displaystyle \sum _{k=0}^{n}F_{k}^{2}=F_{n}F_{n+1}} $
  * 홀수항의 합: $ {\displaystyle \sum _{k=1}^{n}F_{2k-1}=F_{2n}} $
  * 짝수항의 합: $ {\displaystyle \sum _{k=0}^{n}F_{2k}=F_{2n+1}-1} $
  * 위키 링크에는 이 외에도 좀더 다양한 공식들이 적혀있다
    * 위키에는 증명은 생략되어있지만 어렵지 않다. [[https://namu.wiki/w/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98%EC%97%B4#s-4|나무위키]]에서도 찾을수 있다.
  * 관련 문제 
    * [[ps:problems:boj:2086]]
    * [[ps:problems:boj:11440]]

==== 피보나치 수의 최대공약수 ====
  * i번째 피보나치수와 j번째 피보나치수의 최대공약수는 gcd(i,j)번째 피보나치수이다
    * gcd(F(i),F(j)) = F(gcd(i,j))  
    * 여기서 피보나치 수를 세는 것은 1에서 부터 시작한다. 1,2,3,4번째 피보나치 수는 1,1,2,3 이다
  * 증명은 [[https://mono-cake.coffee/2019-08-02-GCD-of-fibonacci/]] 참고
  * 파생되는 유용한 성질들
    * i번째 피보나치수와 j번째 피보나치수가 서로소가 되려면, gcd(i,j)가 1 또는 2이면 된다
    * nk번째 피보나치수는 n번째 피보나치수의 배수이다.
  * 관련 문제 
    * [[ps:problems:boj:11778]] 
    * [[ps:problems:boj:28474]] 


==== Zeckendorf's theorem ====
  * 증명이나 자세한 내용은 [[https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem]] 참고. 아래는 요약.
  * 임의의 자연수를 1개 이상의 distinct하고 연속되지 않은 피보나치 수의 합으로 표현할수 있고, 이 표현은 유일하게 존재한다
    * 이렇게 표현한 것을 Zeckendorf representation이라고 부르고, 이것을 바이너리 형태로 표현한것 (n번째 자리수가 n-th 피보나치 수에 해당) 을 Fibonacci coding 이라고 한다.
  * Zeckendorf representation을 찾는 것은 그리디 알고리즘으로 해결 가능
    * 관련 문제: [[ps:problems:boj:8229]] 
  * Zeckendorf representation은 [[ps:게임 이론]] 에서 Fibonacci Nim 게임의 필승 전략을 구하는 데에도 사용된다.
    * 관련 문제: [[ps:problems:boj:2373]], [[ps:problems:boj:2862]]