WC 考到了，自己却啥也不会，于是做一波斐波那契的题

记 \(F_i\) 为斐波那契数列的第 \(i\) 项
如果题目没特殊说明，这篇博客中默认初始项是 \(F_1=F_2=1\)

各种性质

\[\gcd(F_n,F_{n+1})=1 \]

证明：
根据辗转相减法，有
\(\gcd(F_n,F_{n+1})=\gcd(F_{n+1}-F_n,F_n)=\gcd(F_{n-1},F_n)=\cdots=\gcd(F_1,F_2)=1\)

---

\[\gcd(F_n,F_m)=F_{\gcd(n,m)} \]

证明：
记 \(m=n+k\)
如果把 \(F_p,p>n+1\) 都用 \(F_n\) 和 \(F_{n+1}\) 表示出来，就有：

\[F_{n+2}=1\cdots F_n+1\cdot F_{n+1} \]

\[F_{n+3}=1\cdots F_n+2\cdot F_{n+1} \]

\[F_{n+4}=2\cdots F_n+3\cdot F_{n+1} \]

\[\cdots \]

\[F_{n+k}=F_{k-1}F_n+F_kF_{n+1} \]

那么就有 \(\gcd(F_n,F_m)=\gcd(F_n,F_{k-1}F_n+F_k F_{n+1})=\gcd(F_n,F_k F_{n+1})\)
又因为上一条性质 \(\gcd(F_n,F_{n+1})=1\)，就得到 \(\gcd(F_n,F_m)=\gcd(F_n,F_k)=\gcd(F_n,F_{m-n})\)
然后你发现，把它多迭代几次，就成立在角标上做辗转相减（外面再套一个 \(\gcd\)），那最后一串等下去，就等于了 \(\gcd(F_{\gcd(n,m)},F_{\gcd(n,m)})=F_{\gcd(n,m)}\)
于是得证

题目：

1. P1306 斐波那契公约数，模版，直接矩阵加速
2. CF226C Anniversary
   • 就是转换为求 \(\gcd(a_1,a_2,\cdots,a_k)\) 的最大值
   • 然后就是找到一个最大的 \(x\)，使得 \(x\) 有至少 \(k\) 个倍数出现在 \([l,r]\) 中，也就是 \(\lfloor\dfrac{r}{x}\rfloor-\lfloor\dfrac{l-1}{x}\rfloor \ge k\)
   • 于是可以整除分块枚举 \(\lfloor\dfrac{r}{x}\rfloor\) 的值，如果 \(x\) 当前可取的值是 \([L,R]\)（就是让 \(\lfloor\dfrac{r}{x}\rfloor\) 相同的 \(x\)），那么肯定是让 \(x\) 取到 \(R\)，这样既能让上面的式子尽量大去符号要求，也会让选择更优