1
2
3
4
5
6
7
8
long long ksm(long long a, long long x) {
    long long res = 1;
    while(x) {
        if(x & 1) res = res * a % m;
        a = a * a % m, x >>= 1;
    }
    return res;
}

这是一个**快速幂（Binary Exponentiation / 快速取模幂）**函数，用来计算：

$$
(a^x) \bmod m
$$
逐行直接讲代码逻辑 👇（按你偏好，给结论型解释）

函数整体作用

1
int ksm(int a, int x)

计算 a 的 x 次方，对 m 取模
等价于：pow(a, x) % m，但更快、更安全

变量含义

1
int res = 1;
  • res：保存最终结果
  • 初始为 1，因为乘法单位元是 1

核心循环

1
while(x) {}
  • 只要指数 x > 0 就继续
  • 每一轮把 x 二进制右移一位

判断当前二进制位

1
if(x & 1) res = res * a % m;
  • x & 1：判断 x 的最低位是否为 1
  • 如果是 1，说明当前这一位需要参与乘法
  • 把当前的 a 乘进结果中

对应二进制拆分：
$$
a^{13} = a^{1101_2} = a^8 \cdot a^4 \cdot a^1
$$

底数平方 & 指数右移

1
2
a = a * a % m;
x >>= 1;

  • a = a * a % m
    每一轮把 a 变成：
    $$
    a,\ a^2,\ a^4,\ a^8,\ a^{16}…
    $$

  • x >>= 1
    相当于 x = x / 2，处理下一位二进制

返回结果

1
return res;

最终得到：
$$
res = a^x \bmod m
$$

举个例子（a = 3, x = 5, m = 7）

x(二进制) res a
101 1 3
1 → 乘 3 3
10 3 2
0 3 4
1 → 乘 5 2

结果：3^5 % 7 = 5

为什么用快速幂？

方法 时间复杂度
普通循环 O(x)
快速幂 O(log x) ✅

在**大指数（如 10^9）**时差别巨大

常见使用场景

  • 取模幂运算（竞赛 / 算法题）
  • 费马小定理
  • 逆元计算
  • RSA / 密码学