给我的高精模版改了一下。就是重载乘号里面数的位数和 $500$ 取了个 $\min$。

题解

• 第一问：

用 $\operatorname{len}(n)$ 表示数 $n$ 的位数。

$\operatorname{len}(2^p-1)=\operatorname{len}(2^p)=\lg2\times{p}+1$。

• 第二问：

快速幂高精乘即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 909526;
const double lg2 = log10(2);

struct bigint {
    bool sign;
    vector<int> num;

    bigint() {
        num.clear();
        num.emplace_back(0);
        sign = 0;
    }
    bigint(int x) {
        sign = 0;
        num.clear();
        if (!x) num.emplace_back(0);
        if (x < 0) sign = 1, x = -x;
        while (x)
            num.emplace_back(x % 10),
            x /= 10;
    }
    void pop_back() {num.pop_back();}
    void resize(int x) {num.resize(x);}
    int size() const {return num.size();} 
    int back() const {return num.back();}
    void clear() {num.clear(); sign = 0;}
    void emplace_back(int x) {num.emplace_back(x);}
    int& operator[](int idx) {return num[idx];}
    bool is_zero() {return num.size() == 1 && num[0] == 0;}

    bigint operator- () {
        bigint res = *this;
        return res.sign = !res.sign, res;
    }
    bigint operator= (bigint a) {
        num = a.num, sign = a.sign;
        return *this;
    }
    friend bool operator< (bigint a, bigint b) {
        if (a.sign ^ b.sign) return a.sign;
        if (a.size() != b.size()) return a.sign ^ (a.size() < b.size());
        for (int i = a.size() - 1; ~i; i --)
            if (a[i] != b[i])
                return a.sign ^ (a[i] < b[i]);
        return 0;
    }
    friend bool operator> (bigint a, bigint b) {return b < a;}
    friend bool operator<= (bigint a, bigint b) {return !(b < a);}
    friend bool operator>= (bigint a, bigint b) {return !(a < b);}
    friend bool operator== (bigint a, bigint b) {return a <= b && b <= a;}
    friend bool operator!= (bigint a, bigint b) {return !(a == b);}

    friend bigint operator+ (bigint a, bigint b) {
        if (a.sign && b.sign) return -((-a) + (-b));
        if (!a.sign && b.sign) return a - (-b);
        if (a.sign && !b.sign) return b - (-a);
        bigint res; res.clear();
        int t = 0, l1 = a.size(), l2 = b.size();
        for (int i = 0; i < max(l1, l2); i ++) {
            if (i < l1) t += a[i];
            if (i < l2) t += b[i];
            res.emplace_back(t % 10), t /= 10;
        }
        return (t ? res.emplace_back(t) : void()), res;
    }
    friend bigint operator- (bigint a, bigint b) {
        if (a.sign && b.sign) return a + (-b);
        if (!a.sign && b.sign) return a + (-b);
        if (a.sign && !b.sign) return -((-a) + b);
        if (a < b) return -(b - a);
        bigint res; res.clear();
        int t = 0, l1 = a.size(), l2 = b.size();
        for (int i = 0; i < l1; i ++) {
            t = a[i] - t;
            if (i < l2) t -= b[i];
            res.emplace_back((t + 10) % 10), t = (t < 0);
        }
        while (res.size() > 1 && res.back() == 0)
            res.pop_back();
        return res;
    }
    friend bigint operator* (bigint a, bigint b) {
        if (a.is_zero() || b.is_zero()) return 0;
        bigint res; res.clear();
        res.sign = a.sign ^ b.sign;
        int l1 = a.size(), l2 = b.size();
        res.resize(l1 + l2 + 1);
        for (int i = 0; i < min(500, l1); i ++)
            for (int j = 0; j < min(500, l2); j ++) {
                res[i + j] += a[i] * b[j];
                res[i + j + 1] += res[i + j] / 10;
                res[i + j] %= 10;
            }
            while (res.size() > 1 && res.back() == 0)
                res.pop_back();
        return res;
    }
    friend bigint operator/ (bigint a, int b) {
        bigint res; res.clear();
        res.sign = a.sign ^ (b < 0);
        int t = 0, l1 = a.size();
        res.resize(l1);
        for (int i = l1 - 1; ~i; i --) {
            t = t * 10 + a[i];
            res[i] = t / b; t %= b;
        }
        while (res.size() > 1 && res.back() == 0)
            res.pop_back();
        return res;
    }

    friend void operator+= (bigint &a, bigint b) {a = a + b;}
    friend void operator-= (bigint &a, bigint b) {a = a - b;}
    friend void operator*= (bigint &a, bigint b) {a = a * b;}
    friend void operator/= (bigint &a, int b) {a = a / b;}

    friend bigint max(bigint a, bigint b) {if (a < b) a = b; return a;}
    friend bigint min(bigint a, bigint b) {if (a > b) a = b; return a;}

    friend istream& operator>> (istream& is, bigint &b) {
        string s; is >> s; b.clear();
        if (s[0] == '-') b.sign = 1, s = s.substr(1);
        else b.sign = 0;
        int p = 0;
        while (s[p] == '0') p ++;
        if (p == s.size()) b.emplace_back(0), b.sign = 0;
        for (int i = s.size() - 1; i >= p; i --)
            b.emplace_back(s[i] - '0');
        return is;
    }
    friend ostream& operator<< (ostream& os, bigint b) {
        if (b.sign) os << "-";
        for (int i = b.size() - 1; ~i; i --) os << b[i];
        return os;
    }
};

int P;
bigint res = 1, base = 2;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> P;
    int len = lg2 * P + 1;
    cout << len << '\n';
    for (; P; base *= base, P >>= 1) if (P & 1) res *= base;
    res -= 1;
    for (int i = 500; i; i --) {
        cout << (i > len ? 0 : res[i - 1]);
        if ((500 - i + 1) % 50 == 0) cout << '\n';
    }
    return 0;
}