P1045 [NOIP 2003 普及组] 麦森数

N1tr0us_Acid · 2025-07-13 23:16:20 · 个人记录

upd：交不了题解了，寄。

看了题解区诸多大神的 struct，感觉都很强大。提供一个使用 class 的写法。

\texttt{Solution}

第一问很好搞对吧，求 \log_{10}\left(2^p-1\right)，这个玩意的答案就是 \log_{10}\left(2\right) \times p + 1。

然后第二问显然是个高精度的东西，这里就可以直接用 BigInt 加上快速幂了，注意每输出 50 个数要换行以及最后答案要减一，这里使用最多处理 500 位的方法来保证答案不超过 500 位。

\texttt{Code}

#include <bits/stdc++.h>

using namespace std;

// #define int long long

#define endl '\n'

int n;

class BigInt {
private:
    vector <int> num;
    int f = 1;

public:
    void reset(int k) {
        if(k < 0) this -> f = -1;

        while (k) {
            this -> num.push_back(k % 10);

            k /= 10;
        }

        reverse(this -> num.begin(), this -> num.end());
    }

    void write() {
        int cnt = 0;

        if(this -> f == -1) cout << '-';

        num[0] --; // 注意减一。

        for (int i = 500; i > (int)(this -> num.size()); i --) {
            cout << 0;
            cnt ++;

            if(cnt == 50) {
                cnt = 0;

                cout << endl;
            }
        }

        for (int i = min((int)((this -> num.size()) - 1), 499); i >= 0; i --) {
            cout << this -> num[i];

            cnt ++;

            if(cnt == 50) {
                cnt = 0;

                cout << endl;
            }
        }
    }

    BigInt operator * (BigInt &W) {
        BigInt ans;

        if(W.f + this -> f == 0) ans.f = -1;

        vector <int> tmp(min(505, (int)(W.num.size() + this -> num.size())));

        for (int i = 0; i < min((int)(W.num.size()), 500); i ++) {
            for (int j = 0; j < min((int)(this -> num.size()), 500); j ++) {
                if(i + j >= 500) continue;

                tmp[i + j] += ((this -> num[j]) * W.num[i]);
            }
        }

        for (int i = 1; i <= min((int)(tmp.size() - 1), 500); i ++) {
            tmp[i] += (tmp[i - 1] / 10);

            tmp[i - 1] %= 10;
        }

        ans.num = tmp;

        return ans;
    } 
};

BigInt qpow(int X, int a) {
    BigInt res;
    BigInt x;

    res.reset(1);
    x.reset(X);

    while (a) {
        if(a & 1) res = res * x;

        x = x * x;

        a >>= 1;
    }

    return res;
}

signed main(void) {
    cin >> n;

    cout << (int)(log10(2) * n + 1) << endl;

    BigInt ans = qpow(2, n);

    ans.write();

    return 0;
}