题解：P1226 【模板】快速幂

Yuneko · 2025-03-04 17:59:45 · 题解

题目链接

P1226 【模板】快速幂

题意简述

求 a^b \bmod p 的值。

解题思路

前置知识

两个同底数的数字相乘的结果，比如 a^b \times a^c = a^{b+c}，这一点是显然的，不过多赘述。

原理

发现可以把 b 拆成二进制数。

那么此时对于一个二进制数 x 从低到高每一位的权重为 2^0, 2^1, 2^2, 2^3, \dots, 2^{\lfloor \log x \rfloor}。

也就是说我们只需要求出 a^{2^0}, a^{2^1}, a^{2^2}, a^{2^3}, \dots, a^{2^{\lfloor \log x \rfloor}}，再将所有权重依次相乘即可得到 a^b 的值。

那么我们考虑如何求出这些 a^{2^{0 \sim \lfloor \log x \rfloor}} 这些数字的值。

由于有 2^x \times 2^x = 2^{2x}，那么你发现非常简单的，你可以定义一个变量 y 初始为 x，对于每增加一位，都将 y 重新赋值为 y^2，那么你发现此时根据前面的结论，恰好指数都是 2 的整数次幂，满足了这一条件，因此这个做法是正确的。

时间复杂度为 O(\log b)。

参考代码

只给出快速幂的代码。

ll pw(ll a,ll b,ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%p;
        a=a*a%p;
        b>>=1;  
    }
    return ans;
}