光速幂

· · 算法·理论

光速幂

k 进制倍增

$$a^x \bmod p$$

1. 朴素

基本的欧拉降幂就不说了，可以将 x 缩小到 \varphi(p)\le p 的范围内 .

考虑分块预处理，令 r = \lfloor\sqrt p\rfloor，则我们可以把 a^x 分成几个整块的 a^r 和一个散的

预处理 a^r, (a^r)^2, (a^r)^3, \cdots, , (a^r)^r，a, a^2\cdots, a^r，然后我们就可以求 a^x 力

a_x = a^{rp + q} = (a^r)^p\cdot a^q

这里 rp+q 类似一个带余除法，0\le q < r .

这样空间复杂度 O(\sqrt p)，时间复杂度 O(\sqrt p) - O(1)

这玩意还可以用类似方法搞搞扩域光速幂，矩阵光速幂啥的（不过可能欧拉定理不适用要注意一下）.

Code：

template<int MOD>
struct FastPow
{
private:
    ll p1[66666],p2[66666];
    static ll qpow(ll a,ll n)
    {
        ll ans=1;
        while (n)
        {
            if (n&1) ans=ans*a%MOD;
            a=a*a%MOD; n>>=1;
        } return ans%MOD;
    }
public:
    explicit FastPow(ll a)
    {
        ll t1=a,t2=qpow(t1,65536); p1[0]=p2[0]=1;
        for (int i=1;i<65536;i++) p1[i]=p1[i-1]*t1%MOD;
        for (int i=1;i<65536;i++) p2[i]=p2[i-1]*t2%MOD;
    }
    ll operator()(unsigned n){return p2[n>>16]%MOD*p1[n&65535]%MOD;}
};

例题：块速递推

2. 不朴素

我们这个 r 也不一定取 \sqrt p .

类似快速幂，我们拆

a^x = a^{x\bmod k}\cdot (a^k)^{\lfloor x/k\rfloor}

左边预处理，右边做递归 .

这一般被叫做 k 进制倍增，当 k=2 时等价于快速幂 .

这个可以用来调节预处理复杂度和询问复杂度，例如 r 取 p^{1/3} 时 .

空间复杂度 O(k\log_k p) 时间复杂度 O(k\log_k p) - O(\log_k p)（有错望指正）.

例题：能量采集