计蒜客 T1100：计算2的N次方（高精度乘法详解）

港控/mmm° 2023-03-01 10:10 11阅读 0赞

**上一篇博客：[计蒜客 T1099：大整数减法（高精度减法详解）][T1099]**

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

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  提示
     *  样例输入
     *  样例输出
 *  题解
 *   *  解题思路
     *  解题代码
 *  高精度乘法详解
 *   *  高精度算法简介
     *  大数的存储方式
     *  高精度乘法实现
     *  高精度乘法模板
     *  高精度乘法完整模板

# 题目信息 #

原题连接：[计算2的N次方][2_N]

## 题目描述 ##

任意给定一个正整数 N (N≤100)，计算 2 的 N 次方的值。

## 输入格式 ##

输入一个正整数 N。

## 输出格式 ##

输出 2 的 N 次方的值。

## 提示 ##

高精度计算。

输出时每行末尾的多余空格，不影响答案正确性

## 样例输入 ##

> 5

## 样例输出 ##

> 32

# 题解 #

## 解题思路 ##

使用两个 vector 数组 mul 和 ans 来分别存储 上一次乘以二的结果 和 下一次乘以二 的结果。`首先把 1 放到mul 数组中`，然后进行乘以 2 ，将得出的结果 2 存储到 ans数组中；然后我们将 mul 数组清空，再将上一次乘以 2 的结果存储到 mul 中，然后将 ans 清空来继续下一次循环，重新存储下一次乘以 2 的结果。不断的循环这一步骤直到循环 N 次，即求出 2^N 的结果。最终倒着输出即可。这里关于相乘的具体解释放到后面的高精度乘法详解讲述。先看一下 AC 的代码。

## 解题代码 ##

#include<iostream>
    #include<vector>
    using namespace std;
    
    int main() { 
        int n;
        vector<int> ans, mul;
        cin >> n;
        mul.push_back(1);
        
        for (int i = 0; i < n; i++) { 
            int len = mul.size();
            for (int i = 0, t = 0; i < len || t; i++) { 
                if (i < len) t += mul[i] * 2;
                ans.push_back(t % 10);
                t /= 10;
            }
            
            mul.clear();
            
            int len_ans = ans.size();
            for (int k = 0; k < len_ans; k++) mul.push_back(ans[k]);
    
            ans.clear();
        }
        
        int len = mul.size();
        for (int i = len - 1; i >= 0; i--) printf("%d", mul[i]);
        
        return 0;
    }

# 高精度乘法详解 #

## 高精度算法简介 ##

高精度算法简介已经在之前的博客 [计蒜客T1098:大整数加法(高精度加法详解)][T1098] 中详细的介绍过了，这里就不再赘述了。

## 大数的存储方式 ##

大数的存储方式也在之前的博客 [计蒜客T1098:大整数加法(高精度加法详解)][T1098] 中详细的介绍过了，这里也不再赘述了。这里主要介绍一下高精度乘法的实现方式。

## 高精度乘法实现 ##

这里主要介绍一下一个大整数 A 乘以一个比较小的数 b 的实现方法，两个大整数相乘的实现方法是一样的，不同之处在于两个大数相乘需要将第二个数也拆开分别进行相乘。首先我们定义一个vector数组 ans 来存储相乘之后的结果，定义一个整型变量 t 来存储每次的进位的值。因为是倒着存储的大数，所以在相乘的时候我们从下标为 0 的数字开始相乘依次向后遍历，并且将每次的相应数位相乘的结果放到数组 ans 中。  
 每次相乘之前我们都需要先判断一下数组是否越界了，如果没有越界就使 t 加上当前位乘以较小的数字 b（`注意：因为第二个数字 b 比较小，所以我们直接使 A[i] * b，即大数 A 的每一位数字 直接与 b 相乘，而不需要将 b 拆开，因为 b 比较小，所以我们不需要像大数 A 那样将 A 的每一位拆开进行相乘。` ）。然后将 t % 10 即结果的个位放在当前位置上，然后使 t /= 10 算出进位的值，在下一次循环直接加上该进位的值即可。重复进行这一操作直到将数组 A 中的所有数位乘完，并且检查一下 t 是否进完位，如果相乘结束之后 t 不为 0 ，说明最后一个数位与 b 相乘还是需要进位，那么就继续执行 t % 10,t /= 10 的操作，直到 t = 0为止。  
 最后需要注意`去除结果中的前导零`。因为测试样例中可能会有 A \* 0 的情况，如果不去除前导零会出错。

## 高精度乘法模板 ##

vector<int> mul(vector<int> &A, int b) { 
        vector<int> ans;
        int len = A.size();
        int t = 0;
        for (int i = 0; i < len || t; i++) { 
            if (i < len) t += A[i] * b;
            ans.push_back(t % 10);
            t /= 10;
        }
        // 去除结果中的前导零
        while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
        
        return ans;
    }

## 高精度乘法完整模板 ##

**模板题目链接:[高精度乘法][Link 1]**

#include<iostream>
    #include<vector>
    using namespace std;
    
    vector<int> mul(vector<int> &A, int b) { 
        vector<int> ans;
        int len = A.size();
        int t = 0;
        for (int i = 0; i < len || t; i++) { 
            if (i < len) t += A[i] * b;
            ans.push_back(t % 10);
            t /= 10;
        }
        // 去除结果中的前导零
        while (ans.size() > 1 && ans.back() == 0) ans.pop_back();
        
        return ans;
    }
    
    int main() { 
        string a;
        int b;
        cin >> a >> b;
        vector<int> A;
        
        int len = a.size();
        for (int i = len - 1; i >= 0; i--) A.push_back(a[i] - '0');
        
        vector<int> ans = mul(A, b);
        
        int len_ans = ans.size() - 1;
        for (int i = len_ans; i >=0; i--) printf("%d", ans[i]);
        
        return 0;
    }

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

> 我是ACfun，感谢大家的支持！  
> ![喝杯java冷静一下][java]

[T1099]: https://ac-fun.blog.csdn.net/article/details/107485314
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[2_N]: https://nanti.jisuanke.com/t/T1100
[T1098]: https://ac-fun.blog.csdn.net/article/details/107417161
[Link 1]: https://www.acwing.com/problem/content/795/
[java]: /images/20230209/b3d6d96d088446d2a2091179ab1f8fce.png