zcmimi's blog

arrow_back斐波那契共3篇文章

avatar
zc
2020-10-14 18:06:50

查看原题

点击跳转

结论: \gcd(f_n,f_m)=f_{\gcd(n,m)},然后矩阵快速幂加速即可

证明:

m>n

引理:

  • \gcd(f_n,f_{n+1})=1

    根据辗转相减法, \gcd(f_n,f_{n+1})=\gcd(f_n,f_{n+1}-f_n)=\gcd(f_n,f_{n-1})

    所以 \gcd(f_n,f_{n+1})=\gcd(f_n,f_{n-1})=\dots=\gcd(f_2,f_1)=1

  • f_{n+m}=f_nf_{m-1}+f_{n+1}f_m

    数学归纳法:

    1. n=m=1时,成立
    2. 假设m,n\le k时成立,当n=k+1时:

      \begin{aligned} f_{n+m} &=f_{m+(k+1)}=f_{k+(m+1)}\\ &=f_mf_{k-1}+f_{m+1}f_k\\ &=f_mf_{k-2}+f_{m+1}f_k + f_{m+1}f_{k-1}+f_{m+2}f_k\\ &=f_{m+1}(f_{k}+f_{k-1})+f_{m}(f_{k-1}+f_{k-2})\\ &=f_kf_m+f_{k+1}f_{m+1} \end{aligned}

  • \gcd(f_{n+m},f_n)=\gcd(f_n,f_m)

    \begin{aligned} \gcd(f_{n+m},f_n) &=\gcd(f_nf_{m-1}+f_{n+1}f_m,f_n)\\ &=\gcd(f_{n+1}f_m,f_n)\\ &=\gcd(f_{n+1},f_n)\cdot\gcd(f_m,f_n)\\ &=\gcd(f_m,f_n) \end{aligned}

\begin{aligned} \gcd(f_n,f_m) &=\gcd(f_n,f_{m-n+n})\\ &=\gcd(f_n,f_{m-n}f_{n-1}+f_{m-n+1}f_n)\\ &=\gcd(f_n,f_{m-n}f_{n-1}) \end{aligned} \\ \because \gcd(f_{n},f_{n+1})=1\\ \therefore \gcd(f_n,f_{m-n}f_{n-1})=\gcd(f_n,f_{m-n})

这样一直碾转相减下去,就是f_{\gcd(n,m)}

avatar
zc
2020-07-09 21:41:00
查看原题

点击跳转

拆分为m项时,生成函数为F^m (x)

那么答案的生成函数为\displaystyle G(x)=\sum_{i=0}^{\infin} F^i(x)

F为斐波那契数列生成函数,\displaystyle F(x)=\frac x{1-x-x^2}

\begin{aligned} G(x) &=\sum_{i=0}^{\infty} F^i(x)\\ &=\frac 1{1-F(x)}\\ &=\frac {1-x-x^2}{1-2x-x^2}\\ &=1+\frac x{1-2x-x^2}\\ &=1+\frac x{[1-(1+\sqrt 2)x][1-(1-\sqrt2)x]}\\ &=1+\frac 1{2\sqrt 2}\left( \frac 1{1-(1+\sqrt 2)x} - \frac 1{1-(1-\sqrt 2)x} \right)\\ &=1+\sum_{i=1}^{\infin} \frac{(1+\sqrt 2)^i-(1-\sqrt 2)^i}{2\sqrt 2} x^i \end{aligned}

那么:

\displaystyle ans_n=\frac{(1+\sqrt 2)^n-(1-\sqrt 2)^n}{2\sqrt 2}

其中\sqrt 2 \equiv 59713600 \pmod{10^9+7}(二次剩余)

这样的话:

\displaystyle \begin{aligned} ans_n &=\frac {\sqrt 2}4\left[(1+\sqrt 2)^n-(1-\sqrt 2)^n\right]\\ &\equiv 59713600\times 250000002\times [(1+59713600)^n-(1-59713600)^n] \pmod{10^9+7} \end{aligned}

使用快速幂复杂度O(\log n)

考虑费马小定理: ans_n \equiv ans_{n \mod 10^9+6}

这样就可以把n压到10^9+6以内了,再快速幂即可

avatar
zc
2020-03-15 15:48:00
查看原题

点击跳转

n<m \prod_{i=1}^n \prod_{j=1}^m f_{\gcd(i,j)} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^n \sum_{j=1}^m[\gcd(i,j)=d]} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \sum_{j=1}^{\left \lfloor \frac md \right \rfloor}[\gcd(i,j)=1]} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \mu(i) \left \lfloor \frac n{id}\right \rfloor \left \lfloor \frac m{id}\right \rfloor}

数论分块套数论分块会tle,继续老套路优化

T=id

=\prod_{T=1}^n\sum_{d|T}{f_d}^{\mu(\frac Td) \left \lfloor \frac n{T}\right \rfloor \left \lfloor \frac m{T}\right \rfloor}

可以先预处理出函数s(T)=\sum_{d|T}{f_d}^{\mu(\frac Td)}的前缀积

然后就可以做到数论分块O(\sqrt n)的复杂度了

1/1
Search
search