斐波那契数列
问题 1 求斐波那契数列的第n项
数列的递推公式
F
0
=
0
,
F
1
=
1
F
n
=
F
n
−
1
+
F
n
−
2
F_0 = 0,F_1 = 1\newline F_n = F_{n-1}+F_{n-2}
F
0
=
0
,
F
1
=
1
F
n
=
F
n
−
1
+
F
n
−
2
A
=
[
F
(
n
+
1
)
F
(
n
)
0
0
]
=
[
F
(
1
)
F
(
0
)
0
0
]
[
1
1
1
0
]
n
−
1
A=\\ \begin{bmatrix} F(n+1)&F(n)\\ 0&0 \end{bmatrix}= \begin{bmatrix} F(1)&F(0)\\ 0&0 \end{bmatrix} \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}^{n-1}
A
=
[
F
(
n
+
1
)
0
F
(
n
)
0
]
=
[
F
(
1
)
0
F
(
0
)
0
]
[
1
1
1
0
]
n
−
1
struct Matrix{
int n,m;
#define maxn 10
LL a[maxn][maxn];
Matrix(int n = 2,int m = 2):n(n),m(m){};
};
Matrix m1(2,2),m2(2,2);
Matrix Mutiply(const Matrix &a,const Matrix &b){
Matrix c;
assert(a.m == b.n );
for(int i = 1;i <= a.n; ++i){
for(int j = 1;j <= b.m; ++j){
c.a[i][j] =0;
for(int k = 1;k <= a.m; ++k){
c.a[i][j] =(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j]%mod)%mod;// a.a[i][k]*b.a[]
}
}
}
return c;
}
int main(void)
{
LL n;cin>>n;
m1.a[1][1] = 1;
m1.a[1][2] = 0;
m2.a[1][1] = 1;
m2.a[1][2] = 1;
m2.a[2][1] = 1;
if(n == 0)
puts("0");
else{
n--;
while(n > 0){
if(n&1)
m1 = Mutiply(m1,m2);
n >>= 1;
m2 = Mutiply(m2,m2);
}
cout<<m1.a[1][1]<<endl;
}
return 0;
}
数列的通项公式
在模意义下的
(
5
)
\sqrt(5)
(
5
)
有两个解
383008016
,
616991993
383008016 ,616991993
3
8
3
0
0
8
0
1
6
,
6
1
6
9
9
1
9
9
3
所以这种方法要求解存在，比较局限
LL sqr5 = 383008016;
int main(void)
{
LL n;cin>>n;
LL a = (1+sqr5)*qpow(2,mod-2)%mod;
LL b = (1-sqr5+mod)%mod*qpow(2,mod-2)%mod;
cout<<1ll*qpow(sqr5,mod-2)*(qpow(a,n)-qpow(b,n)+mod)%mod;
return 0;
}
/*
sqrt(5)
383008016
616991993
*/
求解通项的方法 有待补充
斐波那契数列的一些性质
-
gc
d
(
F
(
a
)
,
F
(
b
)
)
=
F
(
g
c
d
(
a
,
b
)
)
gcd(F(a),F(b)) = F(gcd(a,b))
g
c
d
(
F
(
a
)
,
F
(
b
)
)
=
F
(
g
c
d
(
a
,
b
)
)
循环节