题解 洛谷 P1045 [NOIP2003 普及组] 麦森数

简要题意：

给定一个数，求-1的位数和后500位的值，其中。

策略分析：

我们可以将这个问题分为两步来处理，第一步求出位数，第二步求后位 ### 求出位数： 首先有一个非常平凡的结论：的位数为。那么一个的数的位数也等于，设，因为不存在最后一位为的的数，所以的位数一定与的位数相同。我们希望能够将所具有的性质应用在中，设，那么，所以，所以，那么的位数就等于的位数，即，那这不就简单多了，直接库里随便一搞就出来了

求后500位的值：

我们发现一个朴素的高精度乘法的时间复杂度是，那么就寄了，所以我们要用超级快速的高精乘法，C++里什么样的数据类型存的数最大呢？~~（谁刚说__拉出去枪毙分钟）~~显然我们要用 来存储这500位，那么我们就要尽量挑战它的极限，一次乘 （讨厌没有边界感的），这样我们就可以在更短的时间内完成计算

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <cmath>
#define ULL unsigned long long
using namespace std;

namespace Rick { int work() { cout << "Never gonna give you up, never gonna let you down~\n"; } }
namespace SHAWN {
    const int N = 507;
    ULL t[N] = { 1 };
    int p;
    int work()
    {
        cin >> p;
        cout << (int)(log10(2) * p) + 1 << '\n';
        for (; p > 0; p -= 60) {
            ULL jin = 0;
            for (int i = 0; i < 500; ++i) {
                if (p > 60) { t[i] <<= 60; }
                else { t[i] <<= p; }
                t[i] += jin; jin = t[i] / 10; t[i] %= 10;
            }
        }
        t[0] -= 1; 
        // 最开始为了让乘法有值我们设成了1，所以一通操作后要减1
        for (int i = 499; i >= 0; --i) {
            cout << t[i];
            if (! (i % 50)) { cout << '\n'; }
        }
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    // return SHAWN :: work();
    return Rick :: work();
}