快速幂

约 105 个字 19 行代码 预计阅读时间 1 分钟

讲课链接

通常用二进制快速幂，如果卡log，需要光速幂

特别地，$2^k$ 用 1<<k 算最快，如果需要long long类型，则用 1ll<<k，如果溢出，只能用普通快速幂

倍增

$a^n=\begin{cases}a^{n-1}*a&n\%2=1 \\ 1&n=0 \\ a^{n/2}*a^{n/2}&n\%2=0\end{cases}$

int qpow(int a, int n)
{
    if (n == 0)
        return 1;
    if (n&1)
        return qpow(a, n - 1) * a;
    int temp = qpow(a, n/2);//必须，否则算法退化
    return temp * temp;
}

二进制

指数相加等于拿下来相乘，$3^5=3^{2^0+2^2}=3^{2^0} * 3^{2^2}$

long long fast_power(long long base,long long exponent)
{
    long long result=1;
    for(;exponent>0;exponent>>=1)
    {
        if(exponent&1)
            result=result*base;
        base=base*base;
    }
    return result;
}

光速幂

基于分块思想，要求底数和模数固定

$a^b=a^{ks+t}$ ，预处理 $a^0,a^1,a^2,...,a^{s-1}$ 和 $a^0,a^s,a^{2s},...,a^{\lfloor\frac{\phi(p)}{s}\rfloor}$ ，询问 $a^{ks+t}=a^{ks}a^t$

当 $s=\sqrt{\phi(p)}$，预处理复杂度 $O(\sqrt{\phi(p)})$ ，询问复杂度 $O(1)$

const ll mod=114514;
const ll phiMod=114514;
const ll sqrtPhiMod=114514;
const ll base=114514;
ll power1[sqrtPhiMod+3],power2[sqrtPhiMod+3];
void init()
{
    power1[0]=1;
    for(int i=1;i<=sqrtPhiMod;++i)
        power1[i]=power1[i-1]*base%mod;
    power2[0]=1;
    for(int i=1;i<=sqrtPhiMod;++i)
        power2[i]=power2[i-1]*power1[sqrtPhiMod]%mod;
}
ll lightSpeedPower(ll ind)
{
    ind%=phiMod;
    return power1[ind%sqrtPhiMod]*power2[ind/sqrtPhiMod]%mod;
}