[文章目录]
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]的值吗？（ 0 <= a, b, n <= 10^9 ）
n<=10^9.显然用矩乘，不过显然不能直接求乘积，所以我们就矩乘算出指数，再快速幂。
不过指数好大啊，足够写高精度了，额。。。那时间也不够啊。所以我们要用到费马小定理。a^(p-1) ≡1(mod p).（前提是p为质数）所以我们可以将指数MOD一个p-1.（终于知道这个神马定理是干啥的呢）。所以这题用矩乘+快速幂（还有吟唱的数论）。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define MOD 1000000007
#define MOD1 1000000006
using namespace std;
int n;
long long a,b,sum=1;
long long f[3][3],g[3][3];
void work()
{
long long c[3][3];
memset(c,0,sizeof(c));
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
c[i][j]+=g[i][k]*g[k][j]%MOD1;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
g[i][j]=c[i][j]%MOD1;
}
void doit()
{
long long c[3][3];
memset(c,0,sizeof(c));
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
c[i][j]+=f[i][k]*g[k][j]%MOD1;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
f[i][j]=c[i][j]%MOD1;
}
int main()
{
scanf("%lld%lld%d",&a,&b,&n);
f[1][1]=1;
f[2][2]=1;
g[1][2]=1;
g[2][1]=1;
g[2][2]=1;
while(n)
{
if(n&1)
doit();
work();
n>>=1;
}
/*printf("%lld %lld",f[1][1],f[2][1]);*/
while(f[1][1])
{
if(f[1][1]&1)
{
sum*=a;
sum%=MOD;
}
a*=a;
a%=MOD;
f[1][1]>>=1;
}
while(f[2][1])
{
if(f[2][1]&1)
{
sum*=b;
sum%=MOD;
}
b*=b;
b%=MOD;
f[2][1]>>=1;
}
printf("%lld",sum);
return 0;
}