AcWing 89. a^b（快速幂）

墨蓝 2022-11-12 09:35 124阅读 0赞

**上一篇博客：[LeetCode 191. 位1的个数——每日一题][LeetCode 191. _1]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[AcWing 89. a^b][AcWing 89. a_b]

### 文章目录 ###

*  快速幂简介
 *  算法思路
 *  快速幂模板
 *  题目信息
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  数据范围
     *  输入样例
     *  输出样例
 *  题解
 *   *  暴力做法
     *  解题代码
     *  快速幂解法
     *  解题代码

# 快速幂简介 #

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

# 算法思路 #

首先对于任意一个数，都可以使用二进制来表示。比如 **13** 的二进制形式为：**1101**。即 **13 = 1 \* 23 \+ 1 \* 22 \+ 0 \* 21 \+ 1 \* 20**，那么 **313** 就可以表示为  **3 ( 1 ∗ 2 3 + 1 ∗ 2 2 + 0 ∗ 2 1 + 1 ∗ 2 0 ) 3^\{(1 \* 2^3 + 1 \* 2^2 + 0 \* 2^1 + 1 \* 2^0)\} 3(1∗23\+1∗22\+0∗21\+1∗20)** 等价于  **3 1 ∗ 2 3 ∗ 3 1 ∗ 2 2 ∗ 3 0 ∗ 2 1 ∗ 3 1 ∗ 2 0 3^\{1 \* 2^3\} \* 3^\{1 \* 2^2\} \* 3^\{0 \* 2^1\} \* 3^\{1 \* 2^0\} 31∗23∗31∗22∗30∗21∗31∗20**。

这样使用快速幂来计算 **313** 效率就极大的提高了，如果不使用快速幂需要计算 **13** 次，而使用快速幂算法之后只需要计算 **4** 次就可以得出结果。效率非常的高。

那么如何是先快速幂呢？可以使用 `位运算` 中的 `&` 来判断 **指数** 二进制形式的最后一位是否为 **1**，每次循环都使指数 **n** 与 **1** 做 `与运算`，如果结果为 **1**，说明指数的二进制的最后一位为 **1**，此时进行累乘操作。每次判断完成之后都将 `底数` 累计取平方为下一次相乘做准备，比如 **313** 第一次运算为 **3**，第二次为 **32**,第三次为 **(32)2** 即 **34**，以此类推（如果不理解这个操作就模拟一遍计算 **313** 的过程），然后使指数右移（>>）一位，不断的进行右移遍历指数二进制的每一位。

计算快速幂的过程中要注意一个问题，就是需要在累乘的过程中将结果转换为 `long long` 类型的，因为两个 `int` 类型的数据相乘可能会出现数据溢出的情况。为了方便转换可以直接乘上 **1ll**（一个数字1后面跟两个字母l）。

# 快速幂模板 #

// 计算 a^b % p
    int ans = 1 % p;
    while (b) { 
        if (b & 1) ans = ans * 1ll * a % p;
        a = a * 1ll * a % p;
        b >>= 1;
    }

# 题目信息 #

## 题目描述 ##

求 **a** 的 **b** 次方对 **p** 取模的值。

## 输入格式 ##

三个整数 **a,b,p** ,在同一行用空格隔开。

## 输出格式 ##

输出一个整数，表示 **a^b mod p** 的值。

## 数据范围 ##

**0 ≤ a, b ≤ 109**  
 **1 ≤ p ≤ 109**

## 输入样例 ##

> 3 2 7

## 输出样例 ##

> 2

# 题解 #

## 暴力做法 ##

如果直接使用暴力做法的话，假设要算 31024 那么需要计算 **1024** 次，时间复杂度为 **O(n)**。时间复杂度太高，会 `TLE`。

## 解题代码 ##

#include<iostream>
    using namespace std;
    
    int main() { 
        int a, b, p;
        cin >> a >> b >> p;
        int ans = 1 % p;
        for (int i = 0; i < b; i++) { 
            ans = ans * a * 1ll % p; 
        }
        cout << ans;
    }

## 快速幂解法 ##

## 解题代码 ##

#include<iostream>
    using namespace std;
    
    int main() { 
        int a, b, p;
        cin >> a >> b >> p;
        int ans = 1 % p;
        while (b) { 
            if (b & 1) ans = ans * 1ll * a % p;
            a = a * 1ll * a % p;
            b >>= 1;
        }
        cout << ans;
        return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70][]

[LeetCode 191. _1]: https://ac-fun.blog.csdn.net/article/details/115085469
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[AcWing 89. a_b]: https://www.acwing.com/problem/content/91/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20221022/dec62e7641bb430b9306d9210604ce40.png