[NOIP2003-普及] 麦森数

题目描述

给定正整数 $P$ （ $1000 < P \leqslant 3021377$ ），求 $2^P-1$ 的十进制位数，以及它的最后 500 位数字（不足 500 位时高位补 0，每 50 位一行输出）。

思路

位数由公式 $\lfloor P\log_{10}2\rfloor+1$ 直接得出。末 500 位只需计算 $(2^P-1)\bmod 10^{500}$ ，用高精度快速幂在 $O(\log P)$ 次模乘内完成，全程不构造完整大整数。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-10-02 05:18
# update_at: 2026-10-02 05:37

import sys

LOG10_2 = 0.30102999566398119521  # log10(2)，用于浮点估计 2^P 的位数
TAIL_MOD = 10 ** 500              # 只关心十进制最后 500 位


def count_digits(power: int) -> int:
    """2^power - 1 的十进制位数；2^power 不是 10 的幂，与 2^power 位数相同。"""
    digits = int(power * LOG10_2) + 1   # 浮点估计
    two_pow = 1 << power                # 精确值，校正浮点误差（至多偏差 1 位）
    while 10 ** digits <= two_pow:
        digits += 1
    while 10 ** (digits - 1) > two_pow:
        digits -= 1
    return digits


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    power = next(data)  # 输入只有一个整数 P

    digits = count_digits(power)
    # 三参数 pow 模快速幂得 2^P 末 500 位；2^P 不含因子 5，模 10^500 不为 0，减 1 不跨模
    tail = str(pow(2, power, TAIL_MOD) - 1).zfill(500)  # 不足 500 位时高位补 0

    lines = [str(digits)] + [tail[i:i + 50] for i in range(0, 500, 50)]  # 10 行 × 50 位
    sys.stdout.write("\n".join(lines))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115/**
 * 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-10-06 13:02
 * update_at: 2026-10-06 13:02
 */

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

const int DIGITS = 500;          // 需要保留的十进制位数
const int BASE = 10000;          // 每段 4 位十进制
const int L = 125;               // 500 / 4 = 125 段

// a[i] 表示第 i 段（低位在前），只保留前 L 段（共 500 位十进制）
ll a[L], b[L], tmp[L * 2];

// 高精度乘高精度，结果模 10^500（只保留前 L 段）
// res = x * y，x、y 各 L 段
void mul_mod(ll res[], ll x[], ll y[]) {
    memset(tmp, 0, sizeof(tmp));
    for (int i = 0; i < L; ++i) {
        if (x[i] == 0) continue;
        for (int j = 0; j < L; ++j) {
            if (y[j] == 0) continue;
            tmp[i + j] += x[i] * y[j];
        }
    }
    // 进位，只保留前 L 段
    ll carry = 0;
    for (int i = 0; i < L; ++i) {
        ll cur = tmp[i] + carry;
        res[i] = cur % BASE;
        carry = cur / BASE;
    }
    // 更高位丢弃（模 10^500）
}

// 快速幂：计算 2^p mod 10^DIGITS，结果放在 a[]
void pow_mod(int p) {
    // 初始化 a = 1（结果），b = 2（底数）
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    a[0] = 1;
    b[0] = 2;

    while (p > 0) {
        if (p & 1) {
            mul_mod(a, a, b);
        }
        p >>= 1;
        if (p) {
            mul_mod(b, b, b);
        }
    }
}

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

    int P;
    if (!(cin >> P)) return 0;

    // 子问题一：位数 = floor(P * log10(2)) + 1
    long double ld = (long double)P * log10l(2.0L);
    ll digits = (ll)floor(ld) + 1;
    cout << digits << "\n";

    // 子问题二：末 500 位 = (2^P - 1) mod 10^500
    pow_mod(P);

    // 减 1
    a[0] -= 1;
    if (a[0] < 0) {
        a[0] += BASE;
        for (int i = 1; i < L; ++i) {
            a[i] -= 1;
            if (a[i] >= 0) break;
            a[i] += BASE;
        }
    }

    // 转成字符串（高位在前），不足 500 位前面补 0
    string out;
    for (int i = L - 1; i >= 0; --i) {
        char buf[8];
        if (i == L - 1) {
            snprintf(buf, sizeof(buf), "%lld", a[i]);
        } else {
            snprintf(buf, sizeof(buf), "%04lld", a[i]);
        }
        out += buf;
    }

    if ((int)out.length() < DIGITS) {
        out = string(DIGITS - out.length(), '0') + out;
    } else if ((int)out.length() > DIGITS) {
        out = out.substr(out.length() - DIGITS);
    }

    // 每 50 位一行，共 10 行
    for (int i = 0; i < DIGITS; i += 50) {
        cout << out.substr(i, 50) << "\n";
    }

    return 0;
}

[NOIP2003-普及] 麦森数

目录

题目描述

思路

参考代码