题意：求计算fab[n]需要的计算次数MOD B 的结果

首先容易知道的是f[n]=f[n-1]+f[n-2]+1;

1.有 S(n)=F[n+2]-1; S[n]斐波那契数列前n项和。F[n+2]就第n+2项斐波那契数。

证明就直接累加法：

因为A<n+2>=A<n+1>+An
所以An=A<n+2>-A<n+1>

则A<n-1>=A<n+1>-An

A<n-2>=An-A<n-1>

.....

A2=A4-A3

A1=A3-A2

然后再求和Sn=A[n+2]-A2   而A2=1
就是Sn=A[n+2]-1;

2.有f(n)=S(n)-F(n)

证明（来自http://www.cnblogs.com/staginner/archive/2011/12/14/2288187.html）：

先说说我推出f(n)=S(n)-F(n)的过程吧，我们在递推计算递归次数的时候，每次的+1都另起一行来写，这样我们会得到下面的这个表。

    f(0)      f(1)      f(2)      f(3)      f(4)      f(5)      f(6)

                                                                         1

                                                               1         1

                                                     1        1         2

                                          1         1         2         3

                               1         1         2         3         5

         1         1         2         3         5         8         13

    没有数字的地方就可以看做是0，f(i)下面对应的整数和就是f(i)的值，相当于计算f(n)=f(n-1)+f(n-2)+1的时候，每行都进行f(n)=f(n-1)+f(n)的运算，最后再把1另起一行写在上面。

这样我们就能很明显的看出来，每行都是一个斐波那契数列，不难得到f(n)=S(n)-F(n-1)。

最后通过1.2的2个式子就很容易推出 f[n]=2*F[n]-1;

剩下的任务就是计算ans了，由于N很大不能直接递推就用矩阵快速幂来解决可以看这里

http://www.cnblogs.com/Commence/p/3976132.html

代码

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}LL N;int B;struct node{    int mat[2][2];}t,ans;void init(){    t.mat[0][0]=1;t.mat[0][1]=1;t.mat[1][0]=1;t.mat[1][1]=0;    ans.mat[0][0]=1;ans.mat[0][1]=0;ans.mat[1][0]=0;ans.mat[1][1]=1;}node muti(node a,node b){    node res;    for (int i=0;i<2;i++)        for (int j=0;j<2;j++)        res.mat[i][j]=(a.mat[i][0]*b.mat[0][j]+a.mat[i][1]*b.mat[1][j])%B;    return res;}int main(){    int kase=1;    while (scanf("%lld %d",&N,&B)!=EOF)    {        init();        if (N==0 && B==0) break;        printf("Case %d: %lld %d",kase++,N,B);        while (N)        {            if (N&1)  ans=muti(ans,t);            t=muti(t,t);            N>>=1;        }        printf(" %d\n",(ans.mat[0][0]*2-1+B)%B);    }    return 0;}

UVA 10518 How many Calls