HDOJ 4549 - M斐波那契數列 費馬小定理，矩陣乘法

      矩陣乘法求線性關系的數列...而本數列不是線性關系..無法對F(n)構造矩陣直接用矩陣乘法解決...

      不難發現若取log F(n)...則log F(n) = log F(n-1) + log F(n-2)....可以轉化成線性關系...

費馬小定理...描述: 假如p是質數，且(a,p)=1，那麼 a^(p-1) ≡1（mod p）

      本題要注意..提供的1000000007就是質數...且底數a,b,都不會大于等于p...也就是(a,p)與(b,p)恒為1...

      聯系費馬小定裡那麼有對于任意的 a^k %m=a^(k%(m-1)) %m

      推出這個結論..本題就可以通過進行多次矩陣乘法來解決了...

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define oo 1000000007
#define MAXN 1005
using namespace std;
struct node
{
       ll s[2][2];
}p;
node mul(node a,node b)
{
       int i,j,k;
       node h;
       memset(h.s,0,sizeof(h.s));
       for (k=0;k<2;k++)
         for (i=0;i<2;i++)
            for (j=0;j<2;j++)
               h.s[i][j]=(h.s[i][j]+a.s[i][k]*b.s[k][j])%(oo-1);
       return h;
}
ll Fibonacci(int n)
{
       node h;
       h.s[0][0]=h.s[1][1]=1;
       h.s[0][1]=h.s[1][0]=0;
       p.s[0][0]=0;
       p.s[0][1]=p.s[1][0]=p.s[1][1]=1;
       int i;
       for (i=0;i<=30;i++)
       {
              if (n & 1<<i) h=mul(h,p);
              p=mul(p,p);
       }
       return h.s[1][0];
}
ll getdata(ll a,ll n)
{ 
       int i;
       ll p=a,k=1;
       for (i=0;i<=30;i++)
       { 
              if (n & 1<<i) k=(k*p)%oo; 
              p=(p*p)%oo;
       }       
       return k;
}
ll getans(ll a,ll b,ll n)
{
       if (n==0) return a;
       if (n==1) return b;  
       a=getdata(a,Fibonacci(n-1));
       b=getdata(b,Fibonacci(n));
       return a*b%oo;
}
int main()
{     
       ll a,b,n;
       while (~scanf("%I64d%I64d%I64d",&a,&b,&n))
       {
              printf("%I64d\n",getans(a,b,n));
       }
       return 0;
}