快速幂

快快快~

快速幂

问题描述:

  求$A^B$的最后三位数的整数。

分析

如果我们直接通过循环的方法来解决我们会发现

	long long solve(long long base, long long power) {
        long long result = 1;
        
        for (int i = 0; i <= power; ++ i) {
            result = result * base;
      }
        return result % 1000;
}

如果给出$base = 2$ $power = 100$ 的时候我们就就会发现函数$f(x) = a^{b}$是一个指数函数后期的增长速度是非常快的所以我们需要对此进行优化。

取模运算

取模运算有以下 性质:

  1. $(a + b)\%c = ((a\%c) + (b\%c))\%c$

  2. $(a \times b)\%c = ((a\%c) \times (b\%c))\%c$

  3. $(a - b)\%c = ((a\%c)-(b\%c))\%c$

    总成依据话就是,在取模运算的时候我们在中间过程每次都取模,在得出答案之后我们再取一次模。

    我们通过性质性质2来优化我们的代码:

    long long solve(long long base, long long power) {
        long long result = 1;
        for (int i =0; i <= power; ++ i) {
            result *= base;
            result %= 1000;
        }
        return result % 1000;
    }

    通过这样的运算优化,我们发现这种取模运算中如果我们中间进行取模的话是可以防止出现溢出的情况的。

快速幂

  快速幂算法能帮我们算出指数非常大的幂,传统的求幂算法之所以时间复杂度非常高(为O(指数n)),就是因为当指数n非常大的时候,需要执行的循环操作次数也非常大。所以我们快速幂算法的核心思想就是每一步都把指数分成两半,而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小,所需要执行的循环次数也变小,而最后表示的结果却一直不会变。从而达到快速计算的目的。

例如:

$3^{10} = 3\times3\times3\times3\times3\times3\times3\times3\times3\times3$

我们可以尽可能的将其指数降下来,来简化运算。

$3^{10} = (3\times3)\times(3\times3)\times(3\times3)\times(3\times3)\times(3\times3)$

$3^{10} = (3\times3)^5$

其实这种方法也在平常也是十分常见的,比如我们向计算$2^4$我们肯定不会一个一个的乘$2$我们一般都会去直接计算$4\times4$从而快速的计算出结果,其实两者的关系是一样的。

long long solve(int base, int power) {
    long long result = base;
    
    whlie (power > 0) {
        if (power % 2 == 0) {
            //如果指数为偶数
            power /= 2;//把指数缩小为一半
            base = base * base % 1000;//底数变大成原来的平方
        } else {
             //如果指数为奇数
            power = power - 1;//把指数减去1,使其变成一个偶数
            result = result * base % 1000;//此时记得要把指数为奇数时分离出来的底数的一次方收集好
            power /= 2;//此时指数为偶数,可以继续执行操作
            base = base * base % 1000;
        }
    }
    
    return result;
}

最终优化

  我们知到判断奇偶性除了使用 $\%$看其余数是否为$0$ $or$ $1$来进行判断之外,我们还可以通过位运算来进行计算,例如:power&1。因为如果power为偶数,则其二进制表示的最后一位一定是0;如果power是奇数,则其二进制表示的最后一位一定是1。将他们分别与1的二进制做“与”运算,得到的就是power二进制最后一位的数字了,是0则为偶数,是1则为奇数。例如5是奇数,则5&1=1;而6是偶数,则6&1=0;因此奇偶数的判断就可以用“位运算”来替换了。

  同样对于除以$2$的运算我们也可以使用位运算来进行优化power /= 2可以使用右移power = power >> 1实现,右移动1就是除以2,如果右移2就是除以4,同理左移就是乘,左移1就是乘以2左移2就是乘以4;


long long solve(long long base, long long power) {
    long long result = 1;
    while (power > 0) {
        if (power & 1) {//此处等价于if(power%2==1)
            result = result * base % 1000;
        }
        power >>= 1;//此处等价于power=power/2
        base = (base * base) % 1000;
    }
    return result;
}

模板

求$m^k$ $\% $ $p$ 时间复杂度为$O(logk)$

int solve(int m, int k, int p) {
    int res = 1 % p, t = m;
    
    while (k) {
        
        //如果为奇数
        if (k &  1) res = res * t % p;
        
        t = t * t % p;
        k >> 1;
    }
    
    return res;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!