Pilot's Blog
0%

快速幂

发表于 更新于 分类于 ， ， Valine：
本文字数： 636 阅读时长 ≈ 1 分钟
关于蓝桥杯中快速幂的汇总

定义：

核心思想：利用二进制来加速运算

举例说明

计算 \(3^{45}\)

首先把指数45转换为二进制：45(10)=101101(2)

接下来我们可以得到下面的等式

因为

所以我们只需要计算

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
BigInteger quick_power(BigInteger base, BigInteger power) {	//base表示底数，power表示指数
    BigInteger ans = BigInteger.ONE;
    while(power.compareTo(BigInteger.ZERO) > 0) {
        if(power.and(BigInteger.ONE).compareTo(BigInteger.ZERO) < 0) {	
            /*
            	底数与1同或来判断底数的二进制的最后一位是1还是0, 
            	任意一个十进制数，如果是偶数，二进制末尾表示是0;如果是奇数，二进制末尾表示1
            	所以与1同或，如果结果是1，说明原来数的末尾是1，原来的数是奇数; 如果结果是0，说明原来末尾是0，原来的数是偶数			*/
            ans = ans.multiply(base);	//如果最后一位是1，那么就要把当前结果累乘到ans中
        }
        base = base.multiply(base);		//由幂的递归可知下一位的base是当前的平方
        power = power.shiftRight(1);	//将指数右移1位
    }
    return ans;
}

参考文章

举一反三

题目一