HDU - 4549 斐波那契數列 （費馬小定理+快速幂矩陣）

題意：

你會發現a和b的指數變化就是斐波那契數列，再結合費馬小定理,定理應用到這一題就是可以将(A^B)%mod = (A^(B % mod ) )% mod）。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
#define ll long long
const int mo = 1e9 + 6; 
struct node{
  ll m[2][2];
  
};
node cmp(node a, node b){
    node te;
  for(int i = 0; i < 2; i++)
    for(int j = 0; j < 2; j++){
    te.m[i][j]=0;
      for(int k = 0; k< 2; k++){
        te.m[i][j] += a.m[i][k] * b.m[k][j];//；long long防止資料溢出 
        te.m[i][j] %= mo; 
      }
    }
  return te;
}
node powermod(int n){
    node ans,base;
    base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;
      base.m[1][1] = 0;
      ans.m[0][0] = ans.m[1][1] = 1;// ans 初始化為機關矩陣
      ans.m[0][1] = ans.m[1][0] = 0;
      while(n){
        if(n&1) ans = cmp(ans, base);
        n >>= 1;
        base=cmp(base, base);
    }
    return ans;
  }
ll powermod_2(ll a,ll b ,ll c){
  ll ans= 1;
  a = a % c;
  while(b>0){
    if(b%2) ans = (ans * a) %c;
    b = b/2;
    a = (a * a)%c; //若a不為long long溢出 
  }
  return ans;  
} 
 
int main(){
  int a,b,n;
  node te;
  while(scanf("%d%d%d",&a,&b,&n)!= EOF){
    te = powermod(n);
    ll tt=powermod_2(a,te.m[1][1],1e9+7)*powermod_2(b,te.m[1][0],1e9+7);
    printf("%I64d\n",tt%(mo+1));//忘了再取餘一次導緻wa 
  }
  return 0;
}