快速幂与模运算

快速幂与模运算

核心概念

快速幂（二进制取幂）在 $O(\log n)$ 时间内计算 $a^n$，核心思想是将指数按二进制分解：

$$a^n=a^{n_0{2}^0}\times a^{n_1{2}^1}\times \cdots \times a^{n_t{2}^t}$$

模运算性质

• 加法：$(a+b)\mathrm{mod}p=(a\mathrm{mod}p+b\mathrm{mod}p)\mathrm{mod}p$
• 乘法：$(a\times b)\mathrm{mod}p=(a\mathrm{mod}p\times b\mathrm{mod}p)\mathrm{mod}p$
• 幂运算可在中间过程取模

代码实现

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

光速幂（底数固定）

块长 $s=\sqrt{n}$，预处理 $a^0\sim a^{s-1}$ 和 $a^0,a^s,\dots ,a^{\lfloor p/s\rfloor s}$，$O(1)$ 回答查询。

练习题目

题目	描述
P1226 【模板】快速幂	求 $a^b\mathrm{mod}p$
LeetCode 50 Pow(x, n)	实现浮点快速幂
UVa 374 Big Mod	大模快速幂

相关链接

• 素数筛
• GCD与EXGCD
• 中国剩余定理
• 路径D-DSA算法刷题

来源：OI-wiki binary-exponentiation.md

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |