第$k$个斐波那契质数

未分类

---

原题链接：https://code.mi.com/problem/list/view?id=141&cid=9

晚上回集训室的时候师弟问了道题，题意如上$\uparrow$.

简单的说就是对于$f(n)=f(n-1)+f(n-2),f(1)=f(2)=1$ 这个数列，对于$i>2$，如果对所有$2<j<i$都有$gcd(f(i),f(j))=1$,那么称$f(i)$为斐波那契质数，求第$k$个斐波那契质数.

首先先证明一个结论：

$$gcd(f(i),f(j)) = f(gcd(i,j))$$

证明：
显然可以用数学归纳法证明对于所有 $n,k \geq 1$都有：

$$f(n+k) = f(k-1)f(n) + f(k)f(n+1)$$
这里不妨定义$f(0)=0$.
然后显然$gcd(f(n),f(n+1))=1.$
所以$gcd(f(n+k),f(n)) = gcd(f(k)f(n+1),f(n)) = gcd(f(k),f(n))$ .
这里就和辗转相除法如出一辙了，所以有$gcd(f(i),f(j)) = f(gcd(i,j)).$
证毕.

那么我们可以推出：
对于$i>2$，如果$i$是质数，那么显然$f(i)$是斐波那契质数.
如果$i$是合数，当且仅当$i=4$时$f(i)$是斐波那契质数. 下面给出证明：

如果$i=4$显然$f(4)=3$是斐波那契质数.
如果$i$既是合数，又不是$4$，在$[3,i-1]$中一定存在$i$的约数$j$，那么有$f(i)\%f(j)=0,f(j)>1$，可以确定$f(i)$不是斐波那契质数.
证毕.

我们知道只有$f(4)$和满足$i>2$且$i$是质数的$f(i)$是斐波那契质数，要求第$k$个斐波那契质数等同于求第$k$个质数，在$k \leq 500000$时可以线性筛打表质数，然后通过矩阵快速幂或打表斐波那契数求解.

如果$k \leq 10^{9}$的话就是另一道题了，求第$k$个质数可以在接近$O(k^{\frac{2}{3}}logk)$的复杂度做到，原题链接：http://www.51nod.com/Question/Index.html#!#questionId=953.