> 文档中心 > 【蓝桥杯】一学就会的小技巧(三):快速幂

【蓝桥杯】一学就会的小技巧(三):快速幂

header

🍻前言:

  • 一学就会小技巧(一):前缀和
  • 一学就会的小技巧(二):差分
  • 一学就会的小技巧(四):龟速乘
  • 一学就会的小技巧(五):矩阵快速
  • 一学就会的小技巧(六):矩阵快速幂的应用
  • 数论基础—素数筛、最大公约数、最小公倍数
  • 省赛真题—K倍区间(前缀和,数学,思维)

🎈🎈快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N), 与朴素的O(N)相比效率有了极大的提高。

题目传送门🚀🚀🚀

题目 链接
P1226 【模板】快速幂||取余运算 https://www.luogu.com.cn/problem/P1226

🍸快速幂:

👩🏻‍🏫从一道模板题入手来了解快速幂~
题目

⭐常规幂运算的时间复杂度为 O ( N ) O(N) O(N),主要取决于指数的大小。题目中的指数最大可以是 2 31 2^{31} 231,显然在1s内算不出结果,这时就要用到快速幂这个技巧了。

✨如何快速幂呢?✨

  • 以题目中的样例为例,由幂运算的性质, 2 10 2^{10}210可以拆分成 2 5 × 2 5 2^5 \times{2^5}25×25 2 5 2^{5}25可以继续拆分成 2 2 × 2 3 2^{2} \times 2^{3}22×23

  • 再由二进制的运算性质,不妨将指数写成二进制形式, 2 10 2^{10}210 ==> 2 ( 1010 ) 2 2^{(1010)_2}2(1010)2,那么计算 2 10 2^{10}210可以根据指数的二进制形式拆开成:

    2 10= ( 2 1× 0 ) × ( 2 2 × 1 )× ( 2 4 × 0 )× ( 2 8 × 1 )2^{10} = (2^1 \times {0}) \times {(2^2 \times{1})} \times{(2^4 \times 0)} \times{(2^8 \times 1)} 210=(21×0)×(22×1)×(24×0)×(28×1)

    即 : 2 10= ( 2 2× 1 ) × ( 2 8 × 1 )即:2^{10} = (2^2 \times{1}) \times{(2^8 \times 1)} 210=(22×1)×(28×1)

  • 所以,我们可以先将结果设置为1,然后从低位到高位判断二进制形式指数上的每一位(二进制的每一位从第到高分别代表1,2,4,8,16...次幂,换句话说就是第n位二进制数代表 2 n − 1 2^{n-1}2n1次幂)如果是0则跳过,如果是1则将结果乘以底数的 2 n − 1 2^{n-1}2n1次幂。

  • 如何判断每个二进制位是不是1呢?可以通过和1进行与运算的方式,判断最低位是不是1,然后再右移一位依次进行判断。

  • 这种方法的时间复杂度取决于指数二进制形式的位数,为 O(logN) O(logN)O(logN)

  • 题目中还要求我们对结果取模,然而由于幂运算的结果可能很大,在计算过程中就有可能溢出,所以必须在计算过程中就对每一次的计算结果取模。由同余定理可知这样做并不会影响最终结果。

  • 同余定理

    ( a × b )m o d  c = ( am o d  c ) × ( b m o d    c ) m o d  c (a \times b) \mod{c} = (a \mod {c}) \times{(b \mod{c})} \mod c (a×b)modc=(amodc)×(bmodc)modc

🍦模板代码(Java):

import java.util.Scanner;public class Main {    public static long fastPower(long a, long b, long p) { long res = 1; while (b > 0) {     if ((b & 1) == 1)  res = (res * a) % p;     a = (a * a) % p;     b = b >> 1; } return res;    }    public static void main(String[] args) {   Scanner sc = new Scanner(System.in);   int a = sc.nextInt();   int b = sc.nextInt();   int p = sc.nextInt();   sc.close();   long res = fastPower(a, b, p);   System.out.println(a + "^" + b + " mod "+ p+ "=" + res);    }}

🍌🍌🍌
本文介绍了第三个小技巧——快速幂,可以将传统幂运算的O ( N ) O(N) O(N)降低为O ( l o g N ) O(logN) O(logN)~
🍍🍍🍍
创作不易,如果觉得本文对你有所帮助的话请动动小手,给博主点个免费的赞吧。🙇🏻‍♀️
🍉🍉🍉
@作者:Mymel_晗,计科专业大学牲一枚,请大佬们多多关照~

footer

解梦吧