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

这道题目看上去十分简单，只需要算出

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

。

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

CPP

#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;
}

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

文章操作

相关推荐

评论

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