[NOIP 2003 普及组] 麦森数

题意

给定 $P$ ，输出 $2^P-1$ 的十进制位数，以及它的最后 500 位。不足 500 位时在高位补 0，固定输出 10 行，每行 50 位。

$P$ 最大接近 $3.1\times 10^6$ ，完整的 $2^P$ 接近一百万位。题目只询问“位数”和“最后 500 位”，没有必要保存整个数。

思路

朴素写法为什么可能只有部分分

最直接的方法是用一个 500 位数组保存低位，从 1 开始连续乘 $P$ 次 2。超过 500 位的高位随时舍弃，因为它们不会影响最后 500 位。

先看这个适合小数据和对拍的朴素实现：

cpp

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-19 08:59
 * update_at: 2026-07-19 08:59
 */
// brute.cpp：小数据朴素解，逐次乘 2，用来展示部分分做法并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int KEEP_DIGITS = 500;

int p;
int digits[KEEP_DIGITS]; // 低位在前，只保存当前数的最后 500 位

void multiply_by_two() {
    int carry = 0;
    for (int i = 0; i < KEEP_DIGITS; i++) {
        int value = digits[i] * 2 + carry;
        digits[i] = value % 10;
        carry = value / 10;
    }
}

void subtract_one() {
    int pos = 0;
    while (digits[pos] == 0) {
        digits[pos] = 9;
        pos++;
    }
    digits[pos]--;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> p;

    int digit_count = (int)(p * log10(2.0)) + 1;
    cout << digit_count << '\n';

    digits[0] = 1;
    for (int i = 1; i <= p; i++) {
        multiply_by_two();
    }
    subtract_one();

    for (int i = KEEP_DIGITS - 1; i >= 0; i--) {
        cout << digits[i];
        if (i % 50 == 0) cout << '\n';
    }

    return 0;
}

一次乘 2 要扫描 500 个数位，总复杂度为 $O(P\times 500)$ 。当 $P$ 接近 $3.1\times 10^6$ 时，大约要处理 $1.55\times 10^9$ 个数位，这正是逐次乘 2 写法容易只能得到部分分的原因。

位数为什么可以用对数计算

先从十进制位数的定义出发。若正整数 $N$ 恰好有 $d$ 位，那么它满足：

10^{d-1}\leqslant N<10^d.

因为常用对数 $\log_{10}x$ 在 $x>0$ 时单调递增，对不等式三边取常用对数：

d-1\leqslant \log_{10}N<d.

这说明 $\log_{10}N$ 的整数部分恰好是 $d-1$ ，因此：

d=\left\lfloor\log_{10}N\right\rfloor+1.

令 $N=2^P$ ，利用对数的幂运算公式 $\log_a(x^b)=b\log_a x$ ，得到：

\log_{10}(2^P)=P\log_{10}2.

所以 $2^P$ 的位数是：

\left\lfloor P\log_{10}2\right\rfloor+1.

题目求的是 $2^P-1$ ，还要确认减 1 会不会让位数减少。只有当 $2^P$ 恰好等于某个 $10^k$ 时，减 1 才会从 $k+1$ 位变成 $k$ 位；但 $2^P$ 的质因数只有 2，而 $10^k=2^k5^k$ 含有质因数 5，二者不可能相等。因此 $2^P-1$ 与 $2^P$ 位数相同，最终公式为：

text

1digit_count = floor(P * log10(2)) + 1

为什么取模就能得到最后 500 位

令 $M=10^{500}$ 。任意非负整数 $X$ 都可以唯一写成：

X=qM+r,\qquad 0\leqslant r<M.

$qM$ 的十进制末尾至少有 500 个 0，所以 $X$ 的最后 500 位完全由余数 $r=X\bmod M$ 决定。因此本题只需计算：

(2^P-1)\bmod 10^{500}.

模运算与乘法相容：

(a\times b)\bmod M =((a\bmod M)\times(b\bmod M))\bmod M.

所以每次高精度乘法后都可以立即舍弃超过 500 位的高位，不会影响最终答案。

C++：高精度二进制快速幂

把 $P$ 写成二进制后，可以用二进制快速幂计算 $2^P$ ：

answer_digits 初始为 1，base_digits 初始为 2。
若当前指数是奇数，把 base_digits 乘进答案。
将底数平方，指数除以 2。
重复到指数变成 0。

指数每轮至少减半，只需 $O(\log P)$ 轮。数组采用低位在前的顺序，multiply_mod() 用竖式乘法计算两个 500 位数的乘积，只保留下标小于 500 的部分，这就等价于模 $10^{500}$ 。

Python：三参数 `pow`

Python 内置的：

python

1pow(base, exponent, modulus)

会直接进行模快速幂，不会先构造完整的 $2^P$ 。因此后 500 位可以写成：

python

1
2modulus = 10 ** 500
last_digits = (pow(2, P, modulus) - 1) % modulus

str(last_digits).zfill(500) 在左侧补足前导零，再用字符串切片每 50 位输出一行。

正确性说明

位数公式由 $10^{d-1}\leqslant N<10^d$ 取常用对数直接得到； $2^P$ 不可能是 10 的整数次幂，所以减 1 不改变位数。
快速幂始终保持 $2^P\equiv\text{answer}\times\text{base}^{\text{exponent}}\pmod {10^{500}}$ 。指数为奇数时先把一个底数乘入答案，再平方底数并把指数减半，不变量保持成立；指数变成 0 时，答案就是 $2^P$ 的后 500 位。
最后执行减 1，得到 $(2^P-1)\bmod 10^{500}$ ；固定补足 500 位后，输出格式与题目要求一致。

常见失分点

连续执行 $P$ 次高精度乘 2，最大数据下运算次数过多。
先计算完整的 $2^P$ ，没有从“只求最后 500 位”想到取模。
忘记在模幂结果上减 1，或者减 1 时没有处理借位。
输出了不足 500 位的后缀，没有在高位补 0。
没有严格输出 10 行，或每行不是 50 位。

代码

C++17 正式解

cpp

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-19 08:51
 * update_at: 2026-07-19 08:51
 */
#include <bits/stdc++.h>
using namespace std;

const int KEEP_DIGITS = 500;

int p;
int answer_digits[KEEP_DIGITS]; // 低位在前，只保存答案的最后 500 位
int base_digits[KEEP_DIGITS];
int temp_digits[KEEP_DIGITS];

// 计算两个 500 位数的乘积，并舍去超过 500 位的高位。
void multiply_mod(const int a[], const int b[], int result[]) {
    long long product[KEEP_DIGITS] = {0};

    for (int i = 0; i < KEEP_DIGITS; i++) {
        if (a[i] == 0) continue;
        for (int j = 0; i + j < KEEP_DIGITS; j++) {
            product[i + j] += a[i] * b[j];
        }
    }

    for (int i = 0; i < KEEP_DIGITS; i++) {
        if (i + 1 < KEEP_DIGITS) {
            product[i + 1] += product[i] / 10;
        }
        result[i] = product[i] % 10;
    }
}

void copy_digits(int target[], const int source[]) {
    for (int i = 0; i < KEEP_DIGITS; i++) {
        target[i] = source[i];
    }
}

// 二进制快速幂计算 2^p，整个过程只保留最后 500 位。
void fast_power() {
    answer_digits[0] = 1;
    base_digits[0] = 2;

    int exponent = p;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            multiply_mod(answer_digits, base_digits, temp_digits);
            copy_digits(answer_digits, temp_digits);
        }

        multiply_mod(base_digits, base_digits, temp_digits);
        copy_digits(base_digits, temp_digits);
        exponent /= 2;
    }
}

void subtract_one() {
    int pos = 0;
    while (answer_digits[pos] == 0) {
        answer_digits[pos] = 9;
        pos++;
    }
    answer_digits[pos]--;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> p;

    int digit_count = (int)(p * log10(2.0)) + 1;
    cout << digit_count << '\n';

    fast_power();
    subtract_one();

    for (int i = KEEP_DIGITS - 1; i >= 0; i--) {
        cout << answer_digits[i];
        if (i % 50 == 0) cout << '\n';
    }

    return 0;
}

Python 简洁写法

Python 的三参数 pow 已经实现了模快速幂，因此代码会比手写高精度 C++ 短很多：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17from math import log10


KEEP_DIGITS = 500
LINE_WIDTH = 50

p = int(input())
digit_count = int(p * log10(2)) + 1
modulus = 10 ** KEEP_DIGITS
last_digits = (pow(2, p, modulus) - 1) % modulus
text = str(last_digits).zfill(KEEP_DIGITS)

output = [str(digit_count)]
for start in range(0, KEEP_DIGITS, LINE_WIDTH):
    output.append(text[start:start + LINE_WIDTH])

print("\n".join(output))

复杂度

设保留的十进制位数 $K=500$ 。

朴素逐次乘 2：时间复杂度为 $O(PK)$ ，空间复杂度为 $O(K)$ 。
C++ 高精度快速幂：每次竖式乘法为 $O(K^2)$ ，共进行 $O(\log P)$ 次乘法，因此时间复杂度为 $O(K^2\log P)$ ，空间复杂度为 $O(K)$ 。
Python 三参数 pow：进行 $O(\log P)$ 次模乘，参与运算的整数始终限制在模 $10^{500}$ 的范围内；输出额外处理固定 500 个字符。

总结

这道题要把一个巨大整数拆成两个小问题：完整数的位数由对数确定，十进制后缀由模 $10^{500}$ 的余数确定。

C++ 用“高精度乘法 + 二进制快速幂”把逐次乘 2 的 $O(PK)$ 优化为 $O(K^2\log P)$ ；Python 则可以直接使用三参数 pow。最关键的习惯是：题目只问巨大整数的一部分信息时，不要先构造整个巨大整数。