P1045. 麦森数

考点

• 快速幂
• 高精度

题解

#include <bits/stdc++.h>

using namespace std;

const int LEN = 505;

class BigInt
{
public:
    int len_;
    int arr_[LEN];
    int &operator[](int idx)
    {
        return arr_[idx];
    }
    BigInt(int x = 0)
    {
        memset(arr_, 0, sizeof(arr_));
        for (len_ = 1; x; ++len_)
        {
            arr_[len_] = x % 10;
            x /= 10;
        }
        --len_;
    }
    void flatten(int len)
    {
        len_ = len;
        for (int i = 1; i <= len_; ++i)
        {
            if (arr_[i] >= 10)
            {
                arr_[i + 1] += arr_[i] / 10;
                arr_[i] %= 10;
            }
        }
        while (!arr_[len_])
            --len_;
    }
    void print()
    {
        for (int i = 500, cnt = 1; i >= 1; --i, ++cnt)
        {
            cout << arr_[i];
            if (cnt == 50)
            {
                cnt = 0;
                cout << endl;
            }
        }
    }
};

BigInt operator*(BigInt a, BigInt b)
{
    BigInt c;
    for (int i = 1; i <= a.len_; ++i)
    {
        for (int j = 1; j <= b.len_; ++j)
        {
            if (i + j - 1 > 500)
                continue;
            c[i + j - 1] += a[i] * b[j];
        }
    }
    c.flatten(min(500, a.len_ + b.len_));
    return c;
}

BigInt operator*(BigInt a, int b)
{
    BigInt c;
    int len = a.len_;
    for (int i = 1; i <= len; ++i)
    {
        c[i] += a[i] * b;
    }
    c.flatten(min(500, len + 11));
    return c;
}

int main()
{
    int n, p;
    cin >> p;
    n = p;
    BigInt a(2), b(1);
    while (p)
    {
        if (p & 1)
            b = b * a;
        a = a * a;
        p >>= 1;
    }
    cout << (int)(n * log10(2)) + 1 << endl;
    --b[1];
    b.print();
    return 0;
}

思路

使用快速幂的模板套高精乘低精、高精乘高精的模板即可

但是有如下坑点需要注意：

• 因为是2的幂次，最后一位肯定不会小于1；所以减1直接操作最低位自减就行

• 10的幂次可以决定一个数的位数，比如10的2次幂有2 + 1 = 3 位

  且2^P-1的位数与2^p是一样的，实际上是求2^p的位数；那么可以直接通过下列等式得到 \[ \log _{10}2^p+1=P\cdot \log _{10}2+1 \]

• 由于题目说最多只要500位，所以高精度乘法与flatten函数千万不能超过500位导致越界！