记录一道斐波那契数列的算法题

->原题链接见这里<-

注：感谢同济21级数拔 戴先生对一些数学证明的解答，使本人凭借微弱的数学基础也能完成本文的书写🥰

原题重述

题意简述，我们都知道经典的斐波那契数列满足如下性质：

我们记录对于斐波那契数列第n个可以整除k的下标从1开始为，因为可能很大，所以输出时候我们会将结果.

solve the problem

根据补充条件的第一点，我们就可以确定一个循环节，然后在循环节中找到所有的整除的下标问题就解决了（关键在于Pisano周期有很多良好的性质来帮助我们设计一系列最佳算法，后续背景知识非常重要）；

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

#define MODN 1000000007


void solver(ll n,ll k){
    if(k==1){
        cout<<n%MODN<<endl;
        return;
    }
    ll max_loop_length=k*k+2;
    ll feb[3];//记录局部斐波那契数列
    feb[0]=1;feb[1]=1;feb[2]=2;
    ll loop_length=0;
    vector<ll> idxs;

    //接下来确认Pisano周期的长度！
  
    while(max_loop_length-->0)
    {
        if(feb[0]%k==0){
            idxs.push_back(1+loop_length);
        }
        feb[0]=feb[1];feb[1]=feb[2];
        feb[2]=(feb[1]+feb[0])%k;
  
        loop_length++;
        if(feb[0]%k==1&&feb[1]%k==1){
            break;
        }
    }  
  
    ll period_num=n/idxs.size();
    ll period_idx=n%idxs.size();//用于计算目的下标

    // cout<<"========"<<endl;
    // for(auto i:idxs)cout<<i<<endl;
    // cout<<"========"<<endl;
    // printf("loop length= ");
    // cout<<loop_length<<endl;

    ll ans=0;
    if(period_idx==0){
        ans=((((period_num-1)%MODN)*(loop_length%MODN))%MODN+idxs.at(idxs.size()-1))%MODN;
  
    }else{

        ans=(((period_num%MODN)*(loop_length%MODN))%MODN+idxs.at(period_idx-1))%MODN;
  
    }

    cout<<ans<<endl;//最后注意取余和防止溢出

}

int main(){
    ll t,k;
    ll n;
    cin>>t;
    for(ll i=0;i<t;i++)
    {
        cin>>n>>k;
        solver(n,k);
    }
    return 0;
}

也是顺利通过了！

背景知识补充：

What is Pisano Period?

在数论中n阶Pisano周期写作，表征将上述斐波那契数列对n取模之后的周期，这个名字取于Leonardo Pisano. 例如我们如果考虑，我们对斐波那契数列对3取模可以得到：

0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ...

这个序列显然以8为周期，于是.

Pisano周期的存在性证明：

我们考虑，考虑模意义下的斐波那契数列；

基于斐波那契数的递推性质：每一项都只取决于他的前两项，所以我们考虑构造这样的斐波那契数对；构造从 这对：

根据抽屉原理，必定会有完全相等的数对，基于这样的数对便可以循环下去构造出循环节！！！这蕴含了充要条件，也是我们设计算法的关键；

Pisano Period的一些显然或者不显然的性质：

  • 除了以外，Pisano周期都是偶数；【证明见附录proof1】
  • 当m,n互质时，由中国剩余定理即知等于和的最小公倍数。例如，π(3) = 8 而π(4) = 6，由此可得π(12) = 24. 因此，对皮萨诺周期的研究可以化归为对素数幂的皮萨诺周期的研究。
  • 可以证明：如果为素数那么整除；另外有猜想认为对一切素数以及正整数成立。任何不满足该猜想的素数都必然是一个沃尔-孙-孙素数(Wall-Sun-Sun prime)，而这种素数被猜想并不存在。

因此对皮萨诺周期的研究可以被进一步化归为对素数的皮萨诺周期的研究。

斐波那契数列一些性质的整理和证明：

  • 斐波那契数列的递推性质，可以形式化的描述如下：

从而有：

受到快速幂算法的启发，我们可以设计一个矩阵快速幂算法来在的时间复杂度来求得的值（对比之下如果从第一项往后叠加需要的时间复杂度。算法可以使用代码描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>

using namespace std;

// 矩阵乘法
vector<vector<long long>> matrix_mult(const vector<vector<long long>>& A, const vector<vector<long long>>& B) {
    return {
        {
            A[0][0] * B[0][0] + A[0][1] * B[1][0],
            A[0][0] * B[0][1] + A[0][1] * B[1][1]
        },
        {
            A[1][0] * B[0][0] + A[1][1] * B[1][0],
            A[1][0] * B[0][1] + A[1][1] * B[1][1]
        }
    };
}

// 矩阵快速幂
vector<vector<long long>> matrix_pow(vector<vector<long long>> matrix, int n) {
    vector<vector<long long>> result = {{1, 0}, {0, 1}}; // 单位矩阵
    while (n) {
        if (n % 2 == 1) {
            result = matrix_mult(result, matrix);
        }
        matrix = matrix_mult(matrix, matrix);
        n /= 2;
    }
    return result;
}

// 计算第 n 个斐波那契数
long long fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
  
    vector<vector<long long>> F = {{1, 1}, {1, 0}};
    vector<vector<long long>> result = matrix_pow(F, n - 1);
  
    return result[0][0];
}

int main() {
    int n;
    cout << "请输入要计算的斐波那契数的索引 n: ";
    cin >> n;
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}
  • 斐波那契编码

由齐肯多夫定理：任何自然数 n 可以被唯一地表示成一些斐波那契数的和【证明见附录】：

并且这样的编码会满足$ k_{i+1}-k_i，也就是说我们不会使用相邻的两个编码【证明见附录】。斐波那契编码形如d_0d_1d_2d_s1，也就是说两个相邻的代表编码的结尾，如果d_i=1意味着f(i+2)被使用。对正整数n$编码过程的算法伪代码（简单贪心算法）可以描述为：

（1）首先从小到大找到比小的最大斐波那契数；

（2），并且在编码的位置上置1；

（3）如果，重复步骤（1）；

（4）最后在编码的末尾添加上1；

那么：

斐波那契编码有一个有用的特性，有时它与其他通用编码相比更具吸引力：斐波那契编码是自同步编码的一个示例，可以更容易地从损坏的资料流中恢复数据。对于大多数其他通用编码，如果单个比特被更改，则其后的任何数据可能无法被正确读取。另一方面，对于斐波那契编码，更改比特可能会导致一个字词（token）被读取为两个，或者导致两个字词被错误地读取为一个，但从资料流中读取“0”能阻止错误进一步传播。由于唯一没有“0”的资料流是“11”字词的资料流，因此单个比特错误损坏的资料流与原始资料流之间的总编辑距离最多为3。

Appendix

一般线性群

在数学中，n 次一般线性群是 n×n 可逆矩阵的集合，和与之一起的普通矩阵乘法运算。这形成了一个群，因为两个可逆矩阵的乘积也是可逆矩阵，而可逆矩阵的逆元还是可逆矩阵。在 R（实数集）上的一般线性群是实数的 n×n 可逆矩阵的群，并记作为.

proof1 在必定为偶数

这个性质的一个简短证明，考虑斐波那契矩阵:

那么我们应该有：

我们记

从而有

考虑到的相对的任意性(，循环节长度大于等于3意味着你可以任选两个线性无关向量)，于是有：

于是：

两边同时模意义下取行列式可得：

于是在的时候必定会有为偶数。

齐肯多夫定理一些证明：

斐波那契编码不可能相邻，如果相邻那么会导致相邻元素可以用他们后面紧接的元素表示，违背了贪心性质。