数论-快速幂

求 A^B mod C，时间复杂度 O(logB)

模板代码

using ll = long long;  // 可以在头文件中添加这行ll qmi(ll a, ll b, ll c)
{ll ans = 1;       // 初始化结果为 1a %= c;           // 将 a 取模 c，确保 a 小于 cwhile (b)         // 当 b 不为零时循环{if (b & 1)    // 如果 b 是奇数{ans = (ans * a) % c;  // 更新结果}a = (a * a) % c;  // 将 a 平方并取模 cb >>= 1;          // 将 b 右移一位（相当于除以 2）}return ans;          // 返回结果
}

推导过程

要计算 $(a\times b)\mathrm{mod}p$ ，我们已经知道 $a=k_{1}p+q_1$ 和 $b=k_{2}p+q_2$ 。接下来我们先回顾一下 $a\times b$ 的表达式:

$$a\times b=k_1{k}_2{p}^2+\left(k_1{q}_2+q_1{k}_2\right)p+q_1{q}_2$$

现在我们需要对这个结果取模 $p$ ，即计算 $(a\times b)\mathrm{mod}p$ 。
逐项取模:

1. $k_1{k}_2{p}^2\mathrm{mod}p:$

• $p^2$ 是 $p$ 的倍数，所以 $k_1{k}_2{p}^2\mathrm{mod}p=0$ 。

2. $\left(k_1{q}_2+q_1{k}_2\right)p\mathrm{mod}p$ :

• 这一项中有一个 $p$ ，所以也是 $p$ 的倍数，因此 $\left(k_1{q}_2+q_1{k}_2\right)p\mathrm{mod}p=0$ 。

3. $q_1{q}_2\mathrm{mod}p:$

• 这项中不含 $p$ ，所以我们直接取模， $q_1{q}_2\mathrm{mod}p$ 就是结果。

结论:

$$(a\times b)\mathrm{mod}p=q_1{q}_2\mathrm{mod}p$$

因此， $(a\times b)\mathrm{mod}p$ 等于 $q_1{q}_2\mathrm{mod}{p}_{\circ }\downarrow$

例如计算3¹⁰

计算步骤:

1. 初始化:

• ans $=1,a=3,b=10$ (二进制 $1010_2$ ) 。

2. 第一步 $\left(b=1010\_2\right):$

• 最低位为 0 ，跳过乘法。
• 更新 $a=9\left(3^2\right)$ 。

3. 第二步 $\left(b=101\_2\right)$ :

• 最低位为 1 ，乘以 ans $=9\times 3=27$ 。
• 更新 $a=81\left(9^2\right)$ 。

4. 第三步 $\left(b=10\_2\right):$

• 最低位为 0 ，跳过乘法。
• 更新 $a=6561\left(81^2\right)$ 。

5. 第四步 $\left(b=1\_2\right):$

• 最低位为 1 ，乘以 ans $=27\times 6561=177147$ 。
• 更新 $a=43046721\left(6561^2\right)$ 。
• 6. 结果:
• $3^{10}=177147$ 。