斐波那契数列取模（大数）分治算法

斐波那契数列取模（大数）分治算法

这是算法课程上完分之策略后老师留的一道题目：

菲波那契数列如下：1,1,2,3,5,8,13,21,34......其中a[1] = 1, a[2] = 1, a[n]=a[n-1]+a[n-2]（n>=3）。对给定的下标n，求解a[n]%1997的值.

其中测试数据n是整数范围内。

这个题目，主要是用到很关键的一个数学知识，斐波那契数列的求法，可以转换为矩阵的连乘，矩阵的n此方算法又可以用分治的算法。

而且又有理论依据：(n*m)%c=[ (n%c)*(m%c) ]%c ; (n+m)%c=[ (n%c)+(m%c) ]%c ,所以过程中的结果可以随时取模，而不影响最终的结果

关于斐波那契数列的矩阵连乘求法如下：

我们知道我们若要简单计算f(n)，有一种方法就是先保存
a=f(0),b=f(1)，然后每次设：
a'=b b'=a+b

并用新的a'和b'来继续这一运算

如果大家熟悉利用“矩阵”这一工具的话，就知道，如果把a、b写成一个向量[a,b]，完成上述操作相当于乘以矩阵
0 1
1 1
也就是说，如果我们要求第100个fibonacci数，只需要将矩阵
[0,1]乘上
0 1
1 1
的一百次方，再取出第一项

因为我们知道，矩阵运算满足结合律，一次次右乘那个矩阵完全可以用乘上那个矩阵的N次方代替，更进一步，那个矩阵的N次方就是这样的形式：
f(n-1) f(n)
f(n) f(n+1)

而求矩阵的N次方，由于矩阵乘法满足结合律，所以我们可以用log(N)的算法求出——这个算法大家都会么？
一个是二分，一个是基于二进制的求幂

二分的原理：要求矩阵的N次方A(N)，设i=N/2若N%2==1， 则 A(N)=A(i)*A(i)*A(1)若N%2==0， 则 A(N)=A(i)*A(i)

基于二进制的原理：将N拆为二进制数，譬如13=1101那么 A^13= A^8 * A^4 * A^1 （这里^表示幂运算）

也就是说，由A^1开始，自乘得到A^2，然后自乘得到A^4，如果N对应位为1，则将这个结果乘到目标上去

这样的话，将所有乘法改为模乘，就可以得到一个较大Fibonacci数除以M的余数

若不用递归，其实类似

实现代码：

#include<iostream>
using namespace std;
// f(n)=f(i)*f(n-i-1)+f(i+1)*f(n-i)int tempA,tempB,tempC,tempD;
void func(int n,int &a,int &b,int &c,int &d){
    if(n==1){
        a=0;
        b=c=d=1;
        return ;
    }
    if(n%2==0){
        func(n/2,a,b,c,d);
        tempA=a*a+b*c;
        tempB=b*(a+d);
        tempC=c*(a+d);
        tempD=c*b+d*d;
        a=tempA%1997;
        b=tempB%1997;
        c=tempC%1997;
        d=tempD%1997;
        return;
    }
    else{
        func(n/2,a,b,c,d);
        tempA=b*(a+d);
        tempB=a*a+b*(a+c+d);
        tempC=c*b+d*d;
        tempD=c*(a+b+d)+d*d;
        a=tempA%1997;
        b=tempB%1997;
        c=tempC%1997;
        d=tempD%1997;
        return;
    }
}
int main(){
    int n;
    while(cin>>n&&n!=0){
        int a,b,c,d;
        if(n<=2){
            cout<<1<<endl;
            continue;
        }
        else n-=2;
        func(n,a,b,c,d);
        cout<<(b+d)%1997<<endl;
    }    
    return 0;
}