2843: 计算2的N次方 高精度+快速幂

解题思路: 高精度模拟大数乘法，快速幂算法减小复杂度

注意事项: 建议使用结构体，主函数更清晰

参考代码:

#include <iostream>
// #include <sstream>
// #include <cstdio>
// #include <algorithm>
// #include <cmath>
// #include <cstdlib>
#include <cstring>
// #include <cctype>
// #include <string>
// #include <climits>
// #include <map>
// #include <vector>
// #include <list>
// #include <set>
using namespace std;
const int maxn = 1004;
// const long long MOD = 100000007;
// const double PI = acos(-1.0);

const int base = 2; // 乘方底数

struct bigNum {
    int num[ maxn ]; // 倒序存储，num[i]代表base^num[i]
    int len;
   
    bigNum( int digit ) { // 可以设置一个0~9的初始数字
        memset(num, 0, sizeof(num));
        num[0] = digit;
        len = 1;
    }
    bigNum( bigNum &other ) { // copy 拷贝构造函数
        memcpy(num, other.num, maxn * sizeof (int));
        len = other.len;
    }
    void settle() {    // 整理数字，使每一位都在0~9范围内；使len为长度
        int i;
        for (i = 0; i < len || num[i]; i++) {
            if (num[i] >= 10) {
                num[i + 1] += num[i] / 10;
                num[i] %= 10;
            }
        }
        len = i;
        while (num[len - 1] == 0) len--;
    }
    void mul_bigNum( bigNum &mul ) {    // this.num *= mul.num
        int temp[ maxn ];
        memset(temp, 0, sizeof(num));
        for (int i = 0; i < len; i++)
            for (int j = 0; j < mul.len; j++)
                temp[i + j] += num[i] * mul.num[j];
        memcpy(num, temp, maxn * sizeof (int));
        settle();
    }
    void mul_bigNum_self() {    // this.num *= this.num
        bigNum temp(*this);
        mul_bigNum( temp );
    }
    void output() {    // 输出
        for (int i = len - 1; i >= 0; i--)
            cout << num[i];
        cout << endl;
    }
};

bigNum ans(1), m(base);

int main() {
    int n;
    cin >> n;
    while (n) {
        if (n & 1)
            ans.mul_bigNum( m );
        n >>= 1;
        m.mul_bigNum_self();
    }
    ans.output();

    return 0;
}