Solution - P3986 斐波那契数列

P3986 斐波那契数列

idea:

观察性质，应用扩展欧几里得算法。

解决方案：

首先观察到一个性质：由于 $a,b > 0$ ，对于所有 $i\geq 2$ ，有 $f_i > f_{i-1}$ ，故有 $f_{i+1} = f_{i-1} +f_i > 2\cdot f_{i-1}$ 。这说明 $k$ 最多只可能 $O(\log k)$ 项。故 $k$ 出现在第几项是可以枚举的。

然后我们发现：对于所有 $i\geq 2$ ，都可以将 $f_i$ 写成 $p_i\cdot a + q_i\cdot b$ 的形式且 $p_i,q_i>0$ 。不仅如此，还有 $p_i = fib_{i-2}, q_i = fib_{i-1}$ 。这个时候可以使用扩欧求解了。更加让人开心的是，由于 $q_i$ 和 $p_i$ 是 $fib$ 的相邻两项，它们是互质的。

时间复杂度大约是 $O(\log^2 k)$ 。