qpow

¶快速幂

计算数字n^m，直接for循环所消耗时间是O(n)，如果用n²计算n^m则只需计算(n²)^(2/m)，而n²又可以化为n⁴由此可得，只需在判断幂的奇偶性就可以算出结果

通过把底数平方来减少计算次数 消耗时间为O(logn)

• 递归版

typedef long long ll;
ll fastPower(ll n,ll pow){
  ll sum=1;
  if(pow==0)return 1; 
  else if(pow&1){//odd 
    sum *=fastPower(n, pow-1)*n;
  }
  else {//even
    sum*= fastPower(n, pow / 2);//8 4 2 1
    sum *= sum;
  }
  return sum;
}

• 非递归版

在计算n^m时,可以将幂看做二进制来处理，如7¹⁰表示为7^(1010)2
7¹⁰=7² * 7⁸

ll fastPower(ll n,ll pow){
  ll sum=n,ans=1;
  while (pow){
    if (pow & 1) ans *= sum;//当前位为1
    sum *= sum;
    pow >>= 1;//右移1位
  }
  return ans;
}

¶矩阵快速幂

适用于类似斐波那契数列的类型(符号重载)
需要找到一个基础矩阵，通过计算基础矩阵的幂来求得第n项数列的值

洛谷P1962

¶参考

算法学习笔记(4)：快速幂 - Pecco的文章 - 知乎
算法基础 - 数论 | 快速幂、矩阵快速幂、快速乘