【洛谷 1045 && 蓝桥杯算法训练 ALGO - 26】麦森数（二分 + 高精度）

Apr 2, 2020 ｜ # 算法

1 题目

问题描述

形如 $2 ^ {P}-1$ 的素数称为麦森数，这时 $$P$$ 一定也是个素数。但反过来不一定，即如果 $$P$$ 是个素数， $2 ^ {P}-1$ 不一定也是素数。到 1998 年底，人们已找到了 37 个麦森数。最大的一个是 $$P=3021377$$ ，它有 $$909526$$ 位。麦森数有许多重要应用，它与完全数密切相关。
任务：从文件中输入 $$P（1000 < P < 3100000）$$ ，计算 $2 ^ {P}-1$ 的位数和最后 $$500$$ 位数字（用十进制高精度数表示）

输入格式

文件中只包含一个整数 $$P$$ （1000 < P < 3100000）

输出格式

第一行：十进制高精度数 $2 ^ {P}-1$ 的位数。
第 2 - 11 行：十进制高精度数 $2 ^ {P}-1$ 的最后 500 位数字.（每行输出 50 位，共输出 10 行，不足 500 位时高位补 0 ）
不必验证 $2 ^ {P}-1$ 与 $$P$$ 是否为素数。

样例输入

样例输出

386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

2 题目分析

1. 题目难点：

求 $2 ^ {P}-1$ 的位数
高精度算法
二分快速幂实现

2. 求 $2 ^ {P}-1$ 的位数

首先要知道的是 $2 ^ {P}-1$ 与 $2 ^ {P}$ 有相同的位数，因此接下来我们直接求 $2 ^ {P}$ 的位数
不妨设 $k\ =\ 2^{p}$
我们知道， $10^{n}$ 的位数为 $$n+1$$ ，而根据对数运算规则， $10^{\lg 2}\ =\ 2$
因此将 $10^{\lg 2}\ =\ 2$ 代入 $k\ =\ 2^{p}$ 得
$k = 10 ^ {\lg 2 * p}$
所以 $2 ^ {P}$ 的位数为 $p*{\lg 2} +1$
另外，C++ 的 cmath 库中自带 log10() 函数。也有直接计算位数的函数：ceil( n 次方 * log10(底数))

3. 高精度算法

在 C/C++ 中， $$int$$ 类型有 10 位，取值范围为： $-2147483648\sim2147483647$ ； $long\,long$ 类型有 19 位，取值范围为： $-9223372036854775808\sim9223372036854775807$
如果有两个 30 位的数字相乘，应该如何用计算机实现？
这就是高精度乘法的应用，以高精度加法举例，就是用数组存储数字每一位的数字，逐个运算，具体的算法可参考博客：高精度加、减、乘、除算法实现详解
在本题中，就是运用高精度乘法的原理实现二分快速幂过程。

4. 二分快速幂实现

快速幂原理：https://leungll.site/2021/05/24/ksm-permalink
在本题中，用两个函数实现快速幂中 ans *= base 与 base *= base 的功能，其中 $$p$$ 则为幂方 $$b$$ ，数组 b[maxn] 为基数 $$base$$

3 题解

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
//乘法开2倍长度
const int maxn = 1001;
int ans[maxn], b[maxn], carry[maxn], p;

void fun1(){
    memset(carry, 0, sizeof(carry));
    for(int i = 1;i <= 500;i++){
        for(int j = 1;j <= 500;j++){
            carry[i + j - 1] += ans[i] * b[j];
        }
    }
    for(int i = 1;i <= 500;i++){
        carry[i + 1] += carry[i] / 10;
        carry[i] = carry[i] % 10;
    }
    memcpy(ans, carry, sizeof(ans));
}

void fun2(){
    memset(carry, 0, sizeof(carry));
    for(int i = 1;i <= 500;i++){
        for(int j = 1;j <= 500;j++){
            carry[i + j - 1] += b[i] * b[j];
        }
    }
    for(int i = 1;i <= 500;i++){
        carry[i + 1] += carry[i] / 10;
        carry[i] = carry[i] % 10;
    }
    memcpy(b, carry, sizeof(b));
}

int main(){
    int p;
    cin >> p;
    printf("%d\n", (int)( p * log10(2) ) + 1);
    //赋初值 
    ans[1] = 1, b[1] = 2;
    while(p){
        if(p % 2){
            fun1();
        }
        fun2();
        p /= 2;
    }
    //题目要计算的是2 ^ {P} - 1
    ans[1] -= 1;
    for(int i = 500;i > 0;i--){
        if(i != 500 && i % 50 == 0){
            printf("\n%d", ans[i]);
        }else{
            printf("%d", ans[i]);
        }
    }
    return 0;
}

Tags： / C/C++ / 快速幂 / 二分快速幂 / 高精度 / 求位数