P4000 斐波那契数列题解
RaymondFang · · 题解
P4000 斐波那契数列
题目就是要求
约定：题目中的
计算斐波那契数列循环节
结论 1：斐波那契数列对
证明：考虑
共
从而存在
皮萨诺周期（Pisano periods, OEIS A001175）：模
事实上，有
结论 2：若
正确性显然。
Part 1. 当 m 为素数
我们知道斐波那契数列的通项公式
由于里面有一个
结论 3：对于任意奇素数
证明：此时
即周期为
在代码编写当中，判断依据可以写 if(qpow(5,(p-1)/2,mod)==1)。当然，写 if(p%5==1||p%5==4) 是更好的选择。事实上，这种情况下
下面给出证明：由
可以得到
结论 4：对于任意奇素数
证明：此时
对斐波那契数列通项公式进行二项式展开：
那么有
通过观察可以得到模
而又因为
同理，通过二次互反律，可以得到
但是！！！
我们忽略了两种情况。如果
Part 2. 当 m=p^k \ (p \in \mathbb P, k \in \mathbb N)
结论 5：若
事实上，可以通过升幂定理的特殊形式证明：
- 当
p 为奇素数，有v_p(a^{p^k}-1)=v_p(a-1)+v_p(p^k)=v_p(a-1)+k 。而a-1 \equiv 0 \pmod p \Rightarrow v_p(a-1) \ge 1 得到v_p(a^{p^k}-1)\ge k+1 ，即a^{p^k}-1 \equiv 0 \pmod{p^{k+1}} 。 - 当
p=2 ，有v_2(a^{p^k}-1)=v_2(a-1)+v_2(a+1)+v_2(p^k)-1=v_2(a-1)+v_2(a+1)+k-1 。由a \equiv 1 \pmod 2 可得a 为奇数，则a+1 是偶数，也就是v_2(a+1) \ge 1 。所以v_2(a^{p^k}-1) \ge 1+1+k-1=k+1 ，也就是a^{p^k}-1 \equiv 0 \pmod{p^{k+1}} 。
关于升幂定理的内容以及证明见文末。
考虑数学归纳法。令
然而当
即证。
结论 6：对于素数
特别地，
证明：令
所以有
而由 结论 5 可以得到
即证。因为周期等价，所以最小正周期也等价。
换句话说，要求模
Part 3. 当 m 为任意正整数
通过 结论 2
总结
- 对模数
m 进行质因数分解。 - 对于
m 每个p_i^{c_i} ，求出其周期长。 - 求周期长的最小公倍数。
- 把
n 读入后模周期长得到n' ，求出F_{n'} 。
代码
#include<bits/stdc++.h>
using namespace std;
string s;
long long mod;
void read(string& s){
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)){
s+=ch;
ch=getchar();
}
}
long long read(){
long long s=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10+(ch-'0');
ch=getchar();
}
return s*f;
}
void write(const long long& x){
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline long long gcd(long long a, long long b){
if(b==0) return a;
else return gcd(b,a%b);
}
inline long long lcm(long long a, long long b){
return a/gcd(a,b)*b;
}
inline long long qpow(long long a, long long b){
long long ans=1;
while(b){
if(b&1) ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
pair<long long, long long> f(long long k){ // 递推式求斐波那契数列第 n 项，时间复杂度 O(log n)，常数比矩乘小
if(k==0) return {0,1};
pair<long long,long long> p=f(k/2);
long long tp1=p.first*((2*p.second%mod-p.first%mod+mod)%mod)%mod;
long long tp2=(p.first*p.first%mod+p.second*p.second%mod)%mod;
if(k&1) return {tp2,(tp1+tp2)%mod};
else return {tp1,tp2};
}
inline long long getp(long long p){ // 求模 p 意义下周期长
if(p==2) return 3;
else if(p==5) return 20;
else if(p%5==1||p%5==4) return p-1;
else return 2*p+2;
}
inline long long getpk(long long p, long long k){ // 求模 p^k 意义下周期长
return getp(p)*qpow(p,k-1);
}
inline long long get(long long x){ // 求模 x 意义下周期长
long long ans=1;
for(int i=2;i*i<=x;i++){ // 分解质因数
if(x%i==0){
int cnt=0;
while(x%i==0) x/=i,cnt++;
ans=lcm(ans,getpk(i,cnt));
}
}
if(x!=1) ans=lcm(ans,getp(x));
return ans;
}
int main(){
read(s);
mod=read();
if(mod==1){
puts("0");
return 0;
}
long long circle=get(mod);
long long n=0;
for(int i=0;i<s.size();i++) n=(n*10+(s[i]-'0'))%circle;
write(f(n).first);
return 0;
}关于 pair<long long, long long> f(long long) 函数：
这里没有用矩乘，而是用了这个递推式：
而这是极好证明的：
令矩阵
即证。
关于升幂定理
记
-
前提：$n \in \mathbb N_+, p \nmid a, p \nmid b, a \equiv b \pmod p$。则有： $$ v_p(a^n-b^n)=v_p(a-b)+v_p(n) $$ 证明：设 $n=p^km$，其中 $\gcd(p,m)=1$，则 $k=v_p(n)$。 所以 $a^n-b^n=a^{p^km}-b^{p^km}=(a^{p^k}-b^{p^k})(a^{m-1}+a^{m-2}b+\cdots+b^{m-1})$。 而由 $a \equiv b \pmod p$ 得 $a^{m-1}+a^{m-2}b+\cdots+b^{m-1} \equiv m \cdot a^{m-1} \pmod p$，而其中 $p \nmid m, p \nmid a^{m-1}$，所以 $p \nmid ma^{m-1}$。 问题转而分析 $a^{p^k}-b^{p^k}$。若 $k=0$，则 $v_p(a^n-b^n)=v_p(p \cdot ma^{m-1})=1$，$v_p(a-b)+v_p(n)=1+0=1$，命题成立；若 $k>0$，记 $c=a^{p^{k-1}},d=b^{p^{k-1}}$。 则 $a^{p^k}-b^{p^k}=c^p-d^p=(c-d)(c^{p-1}+c^{p-2}d+\cdots+d^{p-1})$。而显然，由 $c \equiv d \pmod p$ 得到 $c^{p-1}+c^{p-2}d+\cdots+d^{p-2} \equiv p\cdot c^{p-1} \equiv 0 \pmod p$，也就是它能被 $p$ 整除。 令 $d=c+rp$。由二项式定理可得： $$ \begin{aligned} c^{p-1}+c^{p-2}d+\cdots+d^{p-1}&=\frac{d^p-c^p}{d-c} \\ &=\frac{(c+kp)^p-c^p}{kp} \\ &=\frac{\dbinom{p}{1}c^{p-1}kp+\dbinom{p}{2}c^{p-2}(kp)^2+\cdots+\dbinom{p}{p}c^0(kp)^p}{kp} \\ &=\dbinom{p}1c^{p-1}+\dbinom{p}2c^{p-2}kp+\cdots+\dbinom{p}p(kp)^{p-1} \\ &\equiv \dbinom{p}1c^{p-1} \pmod{p^2} \\ &\equiv pc^{p-1} \pmod{p^2} \\ &\equiv p(sp+1) \pmod{p^2} \text{ (Fermat's Little Theorem)}\\ &\equiv 1 \pmod{p^2} \end{aligned} $$ 即它不能被 $p^2$ 整除。也就是说，$v_p(c^{p-1}+c^{p-2}d+\cdots+d^{p-1})=1$。从而有 $$ \begin{aligned} v_p(a^{p^k}-b^{p^k})&=v_p(a^{p^{k-1}}-b^{p^{k-1}})+1 \\ &=v_p(a^{p^{k-2}}+b^{p^{k-2}})+2 \\ &=\cdots \\ &=v_p(a^{p^0}-b^{p^0})+k \\ &=v_p(a-b)+v_p(n) \end{aligned} $$ 即证。 -
p=2 前提：
n \in \mathbb N_+ ，且a,b 均为奇数。那么若n 为奇数，则：v_2(a^n-b^n)=v_2(a-b) 若
n 为偶数，则：v_2(a^n-b^n)=v_2(a-b)+v_2(a+b)+v_2(n)-1 证明：设
n=2^km ，其中m 为奇数，则k=v_2(n) 。同理，有a^n-b^n=a^{2^km}-b^{2^km}=(a^{2^k}-b^{2^k})(a^{m-1}+a^{m-2}b+\cdots+b^{m-1}) ，且a^{m-1}+a^{m-2}b+\cdots+b^{m-1} 是奇数。当k=0 ，即n 为奇数，定理显然正确；当k>0 ，同理记c=a^{2^{k-1}},d=b^{2^{k-1}} ，有a^{2^k}-b^{2^k}=c^2-d^2=(c-d)(c+d) ，由c,d 为奇数可得c+d 为偶数。然而当k>1 时c=a^{2^{k-1}}=(a^{2^{k-2}})^2 为平方数，同理d 也为平方数，则c,d \equiv 1 \pmod 4 ，即c+d \equiv 2 \pmod 4 ，因此c+d 中只含一个2 。即\begin{aligned} v_2(a^n-b^n)&=v_2\left(a^{2^k}-b^{2^k}\right) \\ &=v_2(a^{2^{k-1}}-b^{2^{k-1}})+v_2(c+d) \\ &=v_2\left(a^{2^{k-1}}-b^{2^{k-1}}\right)+1 \\ &=v_2\left(a^{2^{k-2}}-b^{2^{k-2}}\right)+2 \\ &= \cdots \\ &=v_2\left(a^2-b^2\right)+(k-1) \end{aligned} 当
k=1 时，a^2-b^2=(a-b)(a+b) ，在\dfrac{a+b}2 和\dfrac{a-b}2 之间必然有一个不被2 整除。这是因为\dfrac{a+b}2-\dfrac{a-b}2=b 是奇数，从而有v_p(a^2-b^2)=v_p(a-b)+v_p(a+b) ，也就是v_2(a^n-b^n)=v_2(a^2-b^2)+(k-1)=v_2(a-b)+v_2(a+b)+v_p(n)-1 即证。