【数学】幂运算与快速幂取余

一、幂运算

1.幂的定义：

的幂就是多个相乘，记作，表示的次幂，即个相乘，我们把叫做底数，叫做指数。

2.幂的运算：

我们可以用公式将幂运算进行简化，公式如下：

3.求幂方法：

(1). Python，C++，Java都有专门求幂的系统函数，用法如下：

python

import math
math.pow(底数, 指数)

 C++

#include 
int main() {
    pow(底数, 指数);
}

 Java

public class Main {
    public static void main(String[] args) {
        Math.pow(底数, 指数);
    }
}

 (2).快速幂

由得，所以指数为奇数是要先把奇数转化为偶数，在进行乘方，算法时间复杂度。

具体代码如下：

python：

def quickPow(base, n):
    ans = 1
    while n > 1:
        if n % 2 == 1:
            ans *= base
        n //= 2
        base **= 2
    return ans * base

C++

int quickPow(int base, int n) {
    int ans = 1;
    while (n > 1) {
        if (n & 1) ans *= base;
        n >>= 2, base *= base;
    }
    return ans * base;
}

二、快速幂取余

1.和差积的模运算：

2.快速幂取余：

一般来说，幂的值很大，题目会让你输出模下的值，这是我们要用快速幂取余，我们只需稍微改动快速幂的代码即可实现。

python

def quickPow(base, n, p):
    base %= p
    ans = 1
    while n > 1:
        if n % 2 == 1:
            ans = ans * base % p
        n //= 2
        base **= 2
        base %= p
    return ans * base % p

C++

int quickPow(int base, int n, int p) {
    long long ans = 1;
    while (n > 1) {
        if (n & 1) ans = ans * base % p;
        n /= 2, base = base * base % p;
    }
    return ans * base % p;
}