以P1226 【模板】快速幂为基准#

前言<快速幂的时间复杂度是>$O(log n)$,暴力乘积取幂的复杂度则为$O(n)$,是一个使用的小技巧,大部分情况下,无需理解原理,背板子即可

原理#

对于一个$n ^ m$的式子,我们可以把$m$拆成$m$的二进制各位相乘,这样根据神秘初二的一个什么什么率(反正我忘了叫啥名了),其计算结果仍不变,但是工作量却少了很多

此处引用下OI-Wiki的例子

假设要计算 $3^{13}$ ．如果将它展开为连乘式，需要 $13-1=12$ 次乘法．但是，因为 $3^{13}=3^{(1101)2}=3^8×3^4×3^1$,所以我们仅需计算$3^8×3^4×3^1$即可

代码实现:#

1
int fastpower(int x, int y,int mod=LLONG_MAX) {
2
  int ans = 1, base = x;
3
  while (y) {
4
    if (y & 1) ans *= base, ans %= mod;
5
    base *= base, base %= mod;
6
    y >>= 1;
7
  }
8
  return ans%mod;
9
}

1
cin >> a >> b >> p;
2
printf("%ld^%ld mod %ld=%ld", a, b, p, fastpower(a, b, p));