解题思路

题目要求计算 2 的 n 次方，n 最大到 100。2^100 有 31 位数字，int 和 long long 都存不下，所以要用高精度：用数组一位一位地存。

思路：

用一个数组 a 存结果的每一位数字，a[0] 存个位，a[1] 存十位……

每次乘 2 就是整个数组的每一位都乘 2，然后处理进位：

1. 把每一位都乘 2
2. 从低位到高位检查，如果某一位超过 10，就向高位进（除以 10 进上去，自身保留余数）
3. 如果最高位产生了新的数字，位数加 1

乘 n 次 2 之后，从高位到低位逆序输出就是答案。

举例 计算 2^5：

• 初始 a = [1]（2^0）
• 乘2：a=[2]
• 乘2：a=[4]
• 乘2：a=[8]
• 乘2：a=[6,1]（16，个位6十位1）
• 乘2：a=[2,3]（32）→ 输出 32

参考代码

#include <iostream>
using namespace std;

int a[100] = {1};  // 存每一位，a[0] 是个位
int k1 = 1;        // 当前位数

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < k1; j++) a[j] = a[j] * 2;  // 每位乘 2

        for (int j = 0; j < k1; j++) {  // 处理进位
            if (a[j] >= 10) {
                a[j + 1] += a[j] / 10;
                a[j] = a[j] % 10;
            }
        }
        if (a[k1] != 0) k1++;  // 产生新的一位
    }

    for (int i = k1 - 1; i >= 0; i--) cout << a[i];  // 逆序输出
    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，n 次乘，每次处理当前位数
• 空间复杂度：O(N)，存每一位数字