题目链接：M斐波那契数列
题意：$F[0]=a，F[1]=b，F[n]=F[n-1]*F[n-2]$。给定$a，b，n$，求$F[n]$。
题解：暴力打表后发现$ F[n]=a^{fib(n-1)} * b^{fib(n)} $
斐波那契数列可用矩阵快速幂求解。但是此题中n较大，fib会爆掉。这时候需要引入费马小定理优化。
证明：$a^x \% p = a^{x \%(p-1)} \%p$
1. $a^x \% p = a^{x \% (p-1) + x/(p-1)*(p-1)} \% p$
2. $a^x \% p = a^{x \% (p-1)} * a^{x/(p-1)*(p-1)} \%p$
3. $a^{x/(p-1)*(p-1)} \% p= ({a^{p-1}}) ^ {(x/(p-1))} \%p = 1^ {(x/(p-1))}$
把3式带入2式，即可证明。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2
using namespace std; typedef long long ll;
const ll mod=; struct mat
{
ll m[N][N]=
{
{,},
{,}
};
}; mat mul(mat a,mat b,ll p)
{
mat ans;
int i,j,k;
for(i=;i<N;i++)
for(j=;j<N;j++)
ans.m[i][j]=; for(i=;i<N;i++)
for(j=;j<N;j++)
for(k=;k<N;k++)
ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%p;
return ans;
} ll matpow(ll n,ll p)
{
if(n<) return ;
mat ans,tmp;
int i,j;
for(int i=;i<N;i++)
for(int j=;j<N;j++)
ans.m[i][j]=; ans.m[][]=;
ans.m[][]=;
while(n)
{
if(n&) ans=mul(tmp,ans,p);
tmp=mul(tmp,tmp,p);
n=n>>;
}
return ans.m[][]%p;
} ll fast_mod(ll a,ll b,ll p){
ll res=;
while(b){
if(b&) res=(res*a)%p;
a=(a*a)%p;
b>>=;
}
return res;
} int main(){
ll n,a,b; while(scanf("%lld%lld%lld",&a,&b,&n)!=EOF){
if(n==){
printf("%lld\n",a);
continue;
}
else if(n==){
printf("%lld\n",b);
continue;
}
else if(a==||b==){
printf("0\n");
continue;
}
ll m1=matpow(n-,mod-);
ll m2=matpow(n,mod-);
ll ans=(fast_mod(a,m1,mod)*fast_mod(b,m2,mod))%mod;
printf("%lld\n",ans%mod);
} return ;
}