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

发布时间：2020-12-14 03:01:29 所属栏目：大数据来源：网络整理

导读：代思路与源代码参考地址在此（1）由于有如下性质： (n*m)%c=[(n%c)*(m%c)]%c (n+m)%c=[(n%c)+(m%c)]%c?, 计算过程中可以随时取模，而不影响最终的结果。（2）利用矩阵求斐波那契数列：（3）二分的原理：要求矩阵的N次方A(N)，设i=N/2。若N%2==1，则 A(

代

思路与源代码参考地址在此

（1）由于有如下性质：

(n*m)%c=[(n%c)*(m%c)]%c

(n+m)%c=[(n%c)+(m%c)]%c?,

计算过程中可以随时取模，而不影响最终的结果。

（2）利用矩阵求斐波那契数列：

（3）

二分的原理：要求矩阵的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;

#define mod 1000000007
// 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 % mod;
        b = tempB % mod;
        c = tempC % mod;
        d = tempD % mod;
        return;
    }
    else{
        func(n / 2,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 % mod;
        b = tempB % mod;
        c = tempC % mod;
        d = tempD % mod;
        return;
    }
}
int main(){
    int n;
    while (cin >> n&&n != 0){
        int a,d;
        if (n <= 2){
            cout << 1 << endl;
            continue;
        }
        else n -= 2;
        func(n,d);
        cout << (b + d) % mod << endl;
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!