题解：P1045 [NOIP 2003 普及组] 麦森数

hyx761 · 2025-06-07 22:35:48 · 题解

这道题目看上去十分简单，只需要算出 2^p-1\mod10^{500} 的值就可以了，看似是一道高精度模板题

但是当我们写好高精度的时候就会发现超时了，P 的最大值会达到 3100000，乘以要维护的 500 位数，就达到了 1.55\times10^9 次的运算。因此我们需要改进。

改进的方法有很多，例如在高精度乘法时不是每次乘以 2，而是 2^n。考虑到 unsigned long long最多只能够表示 2^{64}-1，我们可以每 2^{60} 进行一次乘法，这样所需要的运算次数就降低到了约 2.58\times10^7，已经是在可接受范围内了。

另外计算位数，我们可以通过对数的基本性质：\log_a{b^n}=n\log_ab，把 2^P 的计算回避掉，从而变成 \lfloor p\lg2\rfloor+1。

综上所述，就可以得到以下代码：

#include <iostream>
#include <cmath>
using namespace std;
unsigned long long a[510] = {0, 1}, t;
int p;
int main()
{
    cin >> p;
    cout << (int)(p * log10(2)) + 1 << endl;
    for (; p >= 0; p -= 60)
    {
        t = 0;
        for (int j = 1; j <= 500; j++)
        {
            if (p >= 60) a[j] <<= 60;
            else a[j] <<= p;
            a[j] += t;
            t = a[j] / 10;
            a[j] %= 10;
        }
    }
    a[1] -= 1;
    for (int i = 500; i >= 1; i--) 
    {
        cout << (char)('0' + a[i]);
        if (i % 50 == 1) cout << endl;
    }
    return 0;
}