HDOJ 4549 M斐波那契数列 费马小定理+矩阵高速幂

时间:2023-11-25 17:54:08

MF( i ) = a ^ fib( i-1 ) * b ^ fib ( i )   ( i>=3)

mod 1000000007
是质数 , 依据费马小定理  a^phi( p ) = 1 ( mod p )  这里 p 为质数 且 a 比 p小 所以 a^( p - 1 ) = 1 ( mod p )

所以对非常大的指数能够化简  a ^ k % p  == a ^ ( k %(p-1) ) % p

用矩阵高速幂求fib数后代入就可以

M斐波那契数列

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 1672    Accepted Submission(s): 482

Problem Description
M斐波那契数列F[n]是一种整数数列,它的定义例如以下:



F[0] = a

F[1] = b

F[n] = F[n-1] * F[n-2] ( n > 1 )



如今给出a, b, n,你能求出F[n]的值吗?
Input
输入包括多组測试数据;

每组数据占一行,包括3个整数a, b, n( 0 <= a, b, n <= 10^9 )
Output
对每组測试数据请输出一个整数F[n]。因为F[n]可能非常大,你仅仅需输出F[n]对1000000007取模后的值就可以,每组数据输出一行。
Sample Input
0 1 0
6 10 2
Sample Output
0
60
Source

/* ***********************************************
Author :CKboss
Created Time :2015年03月12日 星期四 22时44分35秒
File Name :HDOJ4549.cpp
************************************************ */ #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map> using namespace std; typedef long long int LL; const LL mod=1000000007LL;
const LL md=1000000006LL; /// getfib
LL a,b,n; struct Matrix
{
Matrix(LL a=0,LL b=0,LL c=0,LL d=0)
{
m[0][0]=a; m[0][1]=b;
m[1][0]=c; m[1][1]=d;
}
LL m[2][2];
}; Matrix MUI(Matrix& a,Matrix& b)
{
Matrix ret;
ret.m[0][0]=((a.m[0][0]*b.m[0][0])%md+(a.m[0][1]*b.m[1][0])%md)%md;
ret.m[0][1]=((a.m[0][0]*b.m[0][1])%md+(a.m[0][1]*b.m[1][1])%md)%md;
ret.m[1][0]=((a.m[1][0]*b.m[0][0])%md+(a.m[1][1]*b.m[1][0])%md)%md;
ret.m[1][1]=((a.m[1][0]*b.m[0][1])%md+(a.m[1][1]*b.m[1][1])%md)%md;
return ret;
} Matrix QUICKPOW(LL m)
{
Matrix E(1,0,0,1);
Matrix A(1,1,1,0);
while(m)
{
if(m&1LL) E=MUI(E,A);
A=MUI(A,A);
m/=2LL;
}
return E;
} void showMat(Matrix M)
{
cout<<endl;
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
cout<<M.m[i][j]<<",";
cout<<endl;
}
cout<<endl;
} /// get p_th fib number
LL getfib(LL p)
{
p--;
Matrix M1=QUICKPOW(p);
return M1.m[0][0];
} LL QUICKPOW2(LL a,LL x)
{
LL e=1LL;
while(x)
{
if(x&1LL) e=(e*a)%mod;
a=(a*a)%mod;
x/=2LL;
}
return e;
} LL solve()
{
if(n==0) return a;
else if(n==1) return b;
else if(n==2) return (a*b)%mod; ///a的fib系数 -> fib(n-1)
LL xa = getfib(n-1);
LL partA = QUICKPOW2(a,xa); ///b的fib系数 -> fib(i)
LL xb = getfib(n);
LL partB = QUICKPOW2(b,xb); return (partA*partB)%mod;
} int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout); while(cin>>a>>b>>n)
cout<<solve()<<endl; return 0;
}