快速幂

2021-12-19 常用算法 数学知识

# 一、算法思想

快速幂,思想是将取幂的任务 按照指数的二进制表示来分割成更小的任务

首先我们将 nn 表示为 2 进制,举一个例子:

313=3(1101)2=383431 3^{13} = 3^{(1101)_2} = 3^8 \cdot 3^4 \cdot 3^1

因为 nnlog2n+1\lfloor \log_2 n \rfloor + 1 个二进制位,因此当我们知道了 x1,x2,x4,x8,,x2log2nx^1, x^2, x^4, x^8, \dots, x^{2^{\lfloor \log_2 n \rfloor}} 后,我们只用计算 Θ(logn)\Theta(\log n) 次乘法就可以计算出 xnx^n

根据以上推导,可把计算 xnx^n 转化为解决以下两个问题:

  • 计算 x1,x2,x4,x8,,x2log2nx^1, x^2, x^4, x^8, \dots, x^{2^{\lfloor \log_2 n \rfloor}} 的值: 循环赋值操作 x=x2x = x^2 即可;
  • 取出指数 n 的二进制中的每一位:当值为 1 时,结果累乘 x。

# 二、算法模板

C++

typedef long long LL;

LL binPow(LL x, LL k)
{
    LL ans = 1;
    while (k) {
        if (k & 1) ans *= x;
        x *= x;
        k >>= 1;
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12

说明

模意义下取幂:取模的运算不会干涉乘法运算,因此我们只需要在计算的过程中取模即可。

# 三、代码实战

# AcWing 0875


题目:快速幂

给定 nnai,bi,pia_i,b_i,p_i,对于每组数据,求出 aibimodpia_{i}^{b_{i}} \bmod p_{i} 的值。

输入格式

第一行包含整数 nn

接下来 nn 行,每行包含三个整数 ai,bi,pia_i,b_i,p_i

输出格式

对于每组数据,输出一个结果,表示 aibimodpia_{i}^{b_{i}} \bmod p_{i} 的值。

每个结果占一行。

数据范围

1n1000001 \le n \le 100000
1ai,bi,pi2×1091 \le a_i,b_i,p_i \le 2 \times 10^9

输入样例:

2

3 2 5

4 3 9

输出样例:

4

1

解答代码:

#include <iostream>

using namespace std;

typedef long long LL;

LL binPow(LL x, LL k, LL p)
{
    LL ans = 1;
    while (k) {
        if (k & 1) ans = ans * x % p;
        x = x * x % p;
        k >>= 1;
    }
    return ans;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    while (n--) {
        LL x, k, p;
        scanf("%lld%lld%lld", &x, &k, &p);
        printf("%lld\n", binPow(x, k, p));
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Last Updated: 2023-01-28 4:31:25

公告

🐳 扫码回复【进群】🐳
🎉 加入 LeetCode 每日打卡交流群 🎉