数论-斐波那契数列的奇怪性质

发表于 2020-10-31 分类于算法，笔记阅读次数：阅读次数： Valine：本文字数： 300

列举了斐波那契数列的各种各样奇怪性质

斐波那契数列求法

1.公式 \[fib(n)=\frac {1}{\sqrt5} \left[\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right]\] 这个一般不用 - 因为太大的double挂了 - 太小的递推好写

2.递推 \[ fib(n)=fib(n-1)+fib(n-2) (n\geq3)\\ fib(1)=1 \\ fib(2)=1 \\ \] 3.矩阵快速幂链接在这里

\[ gcd(F_n,F_m)=gcd(F_{n−m},F_{m}) \\ gcd(F_n,F_m)=F\left(gcd(n,m)\right) \]