题解：P1226 【模板】快速幂

Sk_sync_opener · 2025-03-04 18:46:13 · 题解

首先学过初中数学的都知道 x ^ {2n} = (x ^ {2}) ^ {n}，快速幂就是利用了这个原理，一直把底数平方从而达到快速降次的目的。

那么指数是奇数怎么办呢？我们用一个初值为 1 的变量 ans 记录答案，若当前的指数为奇数，那么将当前的底数乘一个到 ans 里面，从而将指数化为偶数，继续降次。

可以发现通过上面的操作可以直接把答案记录在 ans 里面。

code

int mod;//模数
int qpow(int a, int p) {
  int ans = 1;
  while (p) {
    if (p & 1) (ans *= a) %= mod;
    (a *= a) %= mod;
    p >>= 1;
  }
  return ans;
}