专栏文章

题解:P1226 【模板】快速幂

P1226题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq1q4zi
此快照首次捕获于
2025/12/03 21:31
3 个月前
此快照最后确认于
2025/12/03 21:31
3 个月前
查看原文
首先学过初中数学的都知道 x2n=(x2)nx ^ {2n} = (x ^ {2}) ^ {n},快速幂就是利用了这个原理,一直把底数平方从而达到快速降次的目的。
那么指数是奇数怎么办呢?我们用一个初值为 11 的变量 ansans 记录答案,若当前的指数为奇数,那么将当前的底数乘一个到 ansans 里面,从而将指数化为偶数,继续降次。
可以发现通过上面的操作可以直接把答案记录在 ansans 里面。

code

CPP
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;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...