[算法总结] 快速幂

前言

因为 刚刚在学 逆元 才发现 我对这个 反复平方法这么陌生 所以再重温一遍

算法描述

计算 a^n mod p

a^n = a* a* a*…*a (这种方法 在 a 和 n 太大的时候 就不能用了)

但是我们知道

因此我们可以通过 二进制取幂

因为对于一个数 n 有 log⌊n⌋+1 个 二进制数

所以 a^n 可以拆为

所以我们只需要计算 O( log n ) 次就可以计算出 a^n

CODE:

“>>=1” 表示除2 “b&1” 是表示在b的二进制中的位置正好是1 所以需要统计res(懂了 yes!)

long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}