题解 P4000 【斐波那契数列】
EMT__Mashiro
2018-12-13 22:22:15
2020.4.21：补充了一些注释。
**更好的阅读体验：[PISANO PERIOD](https://www.cnblogs.com/cjoierShiina-Mashiro/p/11385287.html)**
这道题并没有什么花里胡哨的条件，就是很简单的计算$F(n)\ mod\ p$。
但是这题的$n$达到了$10^{30000000}$级别，很显然不能直接用矩阵快速幂做。
因此我们要引入一个概念：斐波那契循环节。
显而易见的是，斐波那契数列在模一个数时会出现循环，而这个周期的长度就称为斐波那契循环节。
所以我们需要先求出斐波那契循环节$m$，然后用矩阵快速幂计算$F(n\ mod\ m)\ mod\ p$就行了。
下面将会介绍如何计算斐波那契循环节。
参考自一篇全英文的paper[The Period of the Fibonacci Sequence Modulo j](https://gradprogram.math.arizona.edu/~ura-reports/071/Campbell.Charles/Final.pdf)
Tips：如果不想看证明过程，可以直接跳到第四部分。
## $1.$定义
### 斐波那契数列
$\forall n\ge 1,F_{n+1}=F_n+F_{n-1}\bigwedge F_0=0,F_1=1,F_2=1$
令$\phi=\frac{1+\sqrt5}{2},\overline{\phi}=\frac{1-\sqrt5}{2}$，易知有$\phi^2=\phi+1$与$\overline{\phi}^2=\overline{\phi}+1$，实际上这就是斐波那契数列的特征方程$x^2=x+1$的两实数根。
由此我们可以推出斐波那契数列的通项公式
$F_n=\frac{1}{\sqrt5}(\phi^n-\overline{\phi}^n)$
（推的方法很多种，可以上百度自己看，这里因为不是重点不做赘述）
### 斐波那契循环节
模$p$意义下的斐波那契数列$F_n(mod\ p)$的循环节$m$是使得$F_m\equiv0(mod\ p)\bigwedge F_{m+1}\equiv1(mod\ p)$的最小正整数$m$。
易知$\forall m| k,F_k\equiv0(mod\ p),F_{k+1}\equiv1(mod\ p)$。
## $2.$第一部分证明
我们需要先证明一些引理。
这一部分的引理和推论都比较简单，可以直接作为结论运用。
### 引理1
设$p$为素数，$n$为非负整数，若$a\equiv1(mod\ p)$，则$a^{p^n}\equiv1(mod\ p^{n+1})$。
**证：**
不妨设$a=rp+1$
运用二项式定理，$a^p\equiv(rp+1)^p\equiv1+\sum\limits_{i=1}^p\left(_i^p\right)(rp)^i\equiv1(mod\ p^2)$
然后数归即可证。
### 推论1
设$p$为素数，$k$为正整数，$m$为$F_n(mod\ p)$的循环节，有$\phi^{mp^{k-1}}\equiv\overline{\phi}^{mp^{k-1}}\equiv1(mod\ p^k)$
**证：**
$\because F_m\equiv0(mod\ p)$
$\therefore\phi^m\equiv\overline{\phi}^m(mod\ p)$
我们知道$F_m=F_{m+1}-F_1=\frac{\phi(\phi^m-1)-\overline{\phi}(\overline{\phi}^m-1)}{\sqrt5}$
用$\phi^m$替换$\overline{\phi}^m$，$F_m\equiv\frac{(\phi^m-1)(\phi-\overline{\phi})}{\sqrt5}\equiv(\phi^m-1)F_1\equiv\phi^m-1\equiv0(mod\ p)$
$\therefore\phi^m\equiv\overline{\phi}^m\equiv1(mod\ p)$
运用**引理1**，$\phi^{mp^{k-1}}\equiv\overline{\phi}^{mp^{k-1}}\equiv1(mod\ p^k)$
### 引理2
设$p$为$5$以外的素数，有$(\frac{5}{p})=1\Leftrightarrow p\equiv\pm1(mod\ 5),(\frac{5}{p})=-1\Leftrightarrow p\equiv\pm2(mod\ 5)$
（这个符号是勒让德符号，含义请百度，此处不作赘述）
**证：**
运用二次互反律，$(\frac5p)(\frac p5)=(-1)^{(\frac{5-1}2)(\frac{p-1}2)}=((-1)^{\frac{p-1}2})^2=1$
运用勒让德符号的定义式，$(\frac5p)=(\frac p5)\equiv p^2(mod\ 5)$
然后把$1$到$4$代进去算就可以证明了。
## $3.$第二部分证明
现在进入中心环节的证明。
这一部分的定理与斐波那契循环节有着更强的联系，实际上将求斐波那契循环节一点点分解然后解决。
### 定理1
设$P=\prod\limits_{i=1}^{s}p_i^{k_i}$，$m_i$为$F_n(mod\ p_i^{k_i})$的循环节，$M$为$F_n(mod\ P)$的循环节，则$M=lcm(m_1,\cdots,m_s)$。
**证：**
$\because F_M\equiv0(mod\ P)$
$\therefore F_M\equiv0(mod\ p_i^{k_i})$
$\therefore\forall i\le s,m_i|M$
$\therefore M=lcm(m_1,\cdots,m_s)$
### 定理2
设$p$为素数，$m$是$F_n(mod\ p)$的循环节，$M$是$F_n(mod\ p^k)$的循环节，则$M| mp^{k-1}$。
**证：**
由**推论1**我们有$\phi^{mp^{k-1}}\equiv\overline{\phi}^{mp^{k-1}}\equiv1(mod\ p^k)$
$\therefore F_{mp^{k-1}}\equiv\frac{\phi^{mp^{k-1}}-\overline\phi^{mp^{k-1}}}{\sqrt5}\equiv0(mod\ p^k)$
$\therefore F_{mp^{k-1}+1}\equiv\frac{\phi^{mp^{k-1}+1}-\overline\phi^{mp^{k-1}+1}}{\sqrt5}\equiv\frac{\phi-\overline{\phi}}{\sqrt5}\equiv1(mod\ p^k)$
即$F_{mp^{k-1}}\equiv0(mod\ p^k)$且$F_{mp^{k-1}+1}\equiv1(mod\ p^k)$
$\therefore M|mp^{k-1}$
### 定理3
设$p$为素数，$m$为$F_n(mod\ p)$的循环节，若$p\equiv\pm1(mod\ 5)$，则$m| p-1$
**证：**
由**引理2**知$5$是$p$的二次剩余，所以可以直接开方（$\sqrt5$在模$p$的数域$\mathbb{F_p}$中）。
运用费马小定理，$\phi^{p-1}\equiv\overline{\phi}^{p-1}\equiv 1(mod\ p)$
$\therefore F_{p-1}\equiv\frac{\phi^{p-1}-\overline\phi^{p-1}}{\sqrt5}\equiv0(mod\ p),F_p\equiv\frac{\phi^p-\overline\phi^p}{\sqrt5}\equiv\frac{\phi-\overline{\phi}}{\sqrt5}\equiv1(mod\ p)$
即$F_{p-1}\equiv0(mod\ p)$且$F_p\equiv1(mod\ p)$
$\therefore m|p-1$
### 定理4
设$p$为素数，$m$为$F_n(mod\ p)$的循环节，若$p\equiv\pm2(mod\ 5)$则$m|2p+2\bigwedge 2\nmid\frac{2p+2}{m}$
**证：**
由**引理2**知$5$不是是$p$的二次剩余，因此不可以直接开方（$\sqrt5$在不在模$p$的数域$\mathbb{F_p}$中）。
所以我们定义一个扩展数域$\mathbb{F_p}(\sqrt5)=\{a+b\sqrt5|a,b\in\mathbb{F_p}\}$。
这里可以理解为类似于从实数域扩展到复数域，然后我们可以证明它满足域的特征。
（这个证明就真没必要纠结了）
利用二项式定理，我们有$(a+b)^p\equiv a^p+b^p(mod\ p)$
$\therefore\phi^p\equiv(\frac12+\frac{\sqrt5}{2})^p\equiv(\frac12)^p+(\frac{\sqrt5}2)^p\equiv(\frac12)^p(1+\sqrt5^p)\equiv\frac12(1+5^\frac{p-1}2\sqrt5)\equiv\frac12(1-\sqrt5)\equiv\overline{\phi}$
同理$\overline{\phi}^p=\phi$
因此我们有
$F_{p}\equiv\frac{\phi^p-\overline\phi^p}{\sqrt5}\equiv\frac{\overline\phi-\phi}{\sqrt5}\equiv p-1(mod\ p)$
$F_{p+1}\equiv\frac{\phi^{p+1}-\overline\phi^{p+1}}{\sqrt5}\equiv\frac{\overline\phi\phi-\phi\overline\phi}{\sqrt5}\equiv0(mod\ p)$
$F_{p+2}\equiv F_p+F_{p+1}\equiv p-1(mod\ p)$
$\therefore m\nmid p+1$
又有
$F_{2p+1}\equiv\frac{\phi^{2p+1}-\overline\phi^{2p+1}}{\sqrt5}\equiv\frac{\overline\phi^2\phi-\phi^2\overline\phi}{\sqrt5}\equiv\frac{\phi\overline\phi(\overline\phi-\phi)}{\sqrt5}\equiv1(mod\ p)$
$F_{2p+2}\equiv\frac{\phi^{2p+2}-\overline\phi^{2p+2}}{\sqrt5}\equiv\frac{\overline\phi^2\phi^2-\phi^2\overline\phi^2}{\sqrt5}\equiv0(mod\ p)$
$F_{2p+3}\equiv F_{2p+1}+F_{2p+2}\equiv1(mod\ p)$
$\therefore m| 2p+2$
又因$m\nmid p+1$
$\therefore 2\nmid\frac{2p+2}{m}$
## $4.$结论
当你看到这部分是你可能还是一脸懵逼，觉得自己只是在跟天书般的数学式子作斗争。但是事实上计算斐波那契循环节的方式已经在第三部分完全给出，下面做一下总结。
### 对于$F_n(mod\ P)$求其循环节$M$总共分$3$步：
### $step1$
由**定理1**，分解质因数$P=\prod\limits_{i=1}^s{p_i^{k_i}}$，求$F_n(mod\ p_i^{k_i})$的循环节$M_i$，然后取$M=lcm(M_1,\cdots,M_s)$
#### $step2$
现在我们将问题转化成了求$F_n(mod\ p_i^{k_i})$的循环节$M_i$。
由**定理2**，$F_n(mod\ p_i^{k_i})$的循环节$M_i$是$p_i^{k_i-1}$乘$F_n(mod\ p_i)$的循环节$m_i$的积$m_ip_i^{k_i-1}$的某一因数。
一个个检查因数会很麻烦，直接取这个$m_ip_i^{k_i-1}$也没有任何问题。因为我们是为了快速计算斐波那契数列的某个值，而$m_ip_i^{k_i-1}$是$M_i$一个倍数，最后得到的"循环节"$\overline M=lcm(m_1p_1^{k_1-1},\cdots,m_sp_s^{k_s-1})$也就会相应地变成正确的循环节$M$的倍数。但是$\overline M$一定是斐波那契数列循环的周期之一。（类似于三角函数最小正周期与周期的关系）。而且这个值也不会很大$(long\ long$范围内$)$，对其取模然后跑矩阵快速幂完全没有问题。
### $step3$
对于每个$p_i$，如果$p_i\le5$，直接打表：$2$的最小循环节是$3,3$的最小循环节是$8,5$的最小循环节是$20$。（这个都手算不出来就有大问题了啊）
若$p_i\equiv\pm1(mod\ 5)$，则$m_i$是$p_i-1$的某一因数，理由同上，直接取本身即可。
若$p_i\equiv\pm2(mod\ 5)$，则$m_i$是$2p+2$的某一因数且$2\nmid\frac{2p+2}{m}$，直接取本身亦可。
下面是远古时期写的代码。
```c++
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e4,S=30000001;
char s[S];
LL pi[N],k[N],P;
inline LL gcd(register LL n,register LL m){while(m^=n^=m^=n%=m); return n;}
inline LL lcm(register LL n,register LL m){return n/gcd(n,m)*m;}
struct matrix
{
LL a[3][3];
matrix(){memset(a,0,sizeof(a));}
matrix operator*(matrix x)
{
matrix s;
for(register int i=1;i<=2;i++) for(register int j=1;j<=2;j++) for(register int k=1;k<=2;k++) s.a[i][j]=(s.a[i][j]+a[i][k]*x.a[k][j])%P;
return s;
}
matrix operator^(register LL k)
{
matrix s=*this,e;
e.a[1][1]=e.a[2][2]=1;
for(;k;k>>=1,s=s*s) if(k&1) e=e*s;
return e;
}
};
inline int power(register LL n)
{
matrix a,ans;
a.a[1][1]=a.a[1][2]=a.a[2][1]=1,a.a[2][2]=0;
ans=a^n;
return ans.a[1][2];
}
inline LL Get(register LL p)
{
register int s=sqrt(p),tot=0;
for(register int i=2;i<=s;++i)
if(!(p%i))
{
pi[++tot]=i,k[tot]=1;
while(!(p%i)) p/=i,k[tot]*=i;
}
for(register int i=1;i<=tot;++i) k[i]/=pi[i];
if(p!=1) k[++tot]=1,pi[tot]=p;
for(register int i=1;i<=tot;++i)
if(pi[i]==2) k[i]*=3;
else if(pi[i]==3) k[i]*=5;
else if(pi[i]==5) k[i]*=20;
else if(pi[i]%5==1||pi[i]%5==4) k[i]*=pi[i]-1;
else k[i]*=(pi[i]+1)<<1;
register LL ans=k[1];
for(register int i=2;i<=tot;++i) ans=lcm(ans,k[i]);
return ans;
}
int main()
{
register int len;
register LL m,n=0;
scanf("%s%lld",s+1,&P),len=strlen(s+1);
if(P==1) return cout<<0,0;
m=Get(P);
for(register int i=1;i<=len;++i) n=((n<<3)+(n<<1)+(s[i]^48))%m;
if(!n) return cout<<0,0;
if(n==1) return cout<<1,0;
return cout<<power(n),0;
}
```