真是恶zhuoer。
前言
本来是在写往年$NOIP$的水题的，然后突然被恶zhuoer丢来了一道题：
这不$SB$题吗？
十分钟切了后，恶zhuoer又丢来一道题：
$emm…$
利用题解+度娘发现斐波那契有很多肥肠神奇的性质。
抄袭来源
https://www.cnblogs.com/Milkor/p/4734763.html
https://blog.csdn.net/m0_37109329/article/details/78481951
http://www.sohu.com/a/280601723_614593
大型懵逼现场
以下所有性质均懒得不予（也不会）证明。
通项公式
$f_n=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right]$
求和
前n项和
$\sum\limits_{i=1}^nf_i=f_{n+2}-1$
前n项平方和
$\sum\limits_{i=1}^nf^2_i=f_nf_{n+1}$
前n项与自然数乘积和
$\sum\limits_{i=1}^nif_i=nf_{n+2}-f_{n+3}+2$
奇数和偶数项和
$\sum\limits_{i=1}^nf_{2i-1}=f_{2n}$
$\sum\limits_{i=1}^nf_{2i}=f_{2n+1}-1$
相邻项乘积之和
$\sum\limits_{i=1}^nf_if_{i+1}=\dfrac{1}{2}\left(f^2_{n+2}-f_nf_{n+1}-1\right)$
各项之间的关系
第n+m项
$f_{n+m}=f_{m-1}f_n+f_mf_{n+1}$
第2n项与第n项
$\dfrac{f_{2n}}{f_n}=f_{n-1}+f_{n+1}$
第奇数项和第偶数项
$f_{2n+1}=f^2_n+f^2_{n+1}$
$f_{2n}=f^2_{n+1}-f^2_{n-1}$
第n-1项与第n+1项的积
$f_{n-1}f_{n+1}=f^2_n+(-1)^n$
第n项与第m项的gcd
$\gcd(f_n,f_m)=f_{\gcd(n,m)}$
整除与斐波那契数列
$n|m\leftrightarrow f_n|f_m$
循环节
模意义下的循环节
记$g(mod)$为模$mod$意义下的最小循环节长度。
$mod$为素数：$g(mod)=\begin{cases}3&mod=2\\8&mod=3\\20&mod=5\\mod-1&\text{5是模mod的二次剩余}\\2(mod+1)&otherwise\end{cases}$
$mod$为素数$p$的$k$次方：$g(mod)=g(mod)\times p^{k-1}$
$mod$为任意正整数：
用算数基本定理分解$mod$：$mod=\sum\limits_{i=1}^cp_i^{k_i}$
$g(mod)=\operatorname{lcm}\limits_{i=1}^cg(p_i^{k_i})$
末位循环
个位：周期$60$
后两位：周期$300$
后三位：周期$1500$
