【算法】快速幂

Rosemary_dream · 2022-07-20 20:22:55 · 个人记录

本文主要介绍快速幂及其用法。

快速幂（bin _pow）： 一种用于快速的求解大指数幂的算法，基于 二进制拆分 。

第一部分

首先介绍 二进制拆分 。我们知道，对于任意一个数，皆可被表示为多个二的幂的和。举个例子如下：

648=2^9+2^7+2^3 7=2^2+2^1+2^0

第二部分

对于一个数的任意次幂，我们可以进行以下的拆分：

a^b=a^c*a^d\ \ (a=c+d)

那么，由第一部分的学习可得，任意一个数皆可被拆分为若干二的任意次幂来表示，我们就可以对 b 进行拆分，具体如何进行见下。

ll bin_pow(ll a,ll b){
    ll re=1,bit=a;//re为返回值，bit为每次自乘值
    while(b>0){//只要b还大于0就 不--要--停--下--来--啊--（雾）
        if(b&1) re*=bit,bit*=bit
            else bit*=bit;
        b>>=1;//进制位右移，等价于 ÷2 
    }
    return re;
}

解释一下 b>>=1 这一句，我们来进行一个手的模 （雾）

对于 5^7 而言， 7 的 二进制表示为 0111 ，在数次循环中， b 的值分别为 b=4,b=2,b=1 ,而代码中 b&1 的限制保证了只有在 b=1 时才会对 re 进行处理，其余时候， bit 会自乘，所以对于 bit 的变化应为 bit=5,bit=25，bit=625 。

注意画了下划线的二进制部分，此为 re*=bit 的时刻。

不过呢，一般使用到快速幂的情况下，指数都大得离谱如 114514^{1919810} （bushi），所以快速幂一般配合着 mod 某个数来使用。只需加在 re*=bit 和 bit*=bit 处就好了。

ll bin_pow(ll a,ll b){
    ll re=1,bit=a;
    while(b>0){
        b&1?re*=bit,bit*=bit:bit*=bit;
        b>>=1;
    }
    return re;
}