题目描述

形如 $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是否为素数。

输入输出样例

输入 #1

1279

输出 #1

386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

题目分析

题目需要我们解决两个问题

  1. 位数
  2. 最后500位数字

​ 首先对于位数,我们 $2^p-1$ 的位数一定与 $2^p$ 的位数相同,因为 $2^p$ 不可能出现个位为0的情况。所以只需要求 $2^p$ 的位数即可。

对于十进制数字$x$,它对应的位数为 $\lfloor \log_{10}^x + 1\rfloor$,所以$2^p$ 的位数为 $\lfloor \log_{10}^{2^p}+1\rfloor$。

已知对数公式

$$ \log_a^{b^c}=c\log_a^b $$

所以

$$ \log_{10}^{2^p}=p\log_{10}^2 $$

所以 $2^P$的位数等于 $\lfloor p\log_{10}^2+1\rfloor$ 。而cmath存在函数log10(x) 可以求解 $log_{10}x$ 的值。

所以位数等于int(p*log10(2)+1)

​ 其次,再来解决第二个问题。求后500位的内容。500位的数字对于现有的整数类型来说还是太大了,所以采用高精度的方式处理,而且我们每次只需处理后500位即可。将高精度乘二的过程重复p次即可。理论上的执行次数是 $500p$ 。而本题中p的范围的限制,导致总的次数达到 $1.5 \times 10^9 $ 。

​ 此时,可以考虑压位高精的方式进行处理,使用 long long 类型,每个元素保留10位的数字,500 位数字,只需50个元素即可,降低总次数至 $10^8$ 的量级,即可满足题目要求。

代码实现

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 M = 1e10;
int p;
i64 num[55]={1};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>p;
    for(int i=1;i<=p;i++){//计算2^p ,压位高精
      int jw=0;
      for(int j=0;j<50;j++){//逐位乘2
        num[j]=jw+num[j]*2;
        jw=num[j]/M;
        num[j]%=M;
      }
    }
    num[0]-=1;//求2^p - 1,最低位减1
    printf("%d\n",(int)(p*log10(2)+1));//计算位数
    for(int i=49;i>=0;i--){//从高位输出,10位一组,不足10位用0补齐
      printf("%010lld",num[i]);
      if(i%5==0) printf("\n");//50个一行
    }
    return 0;
}

快速幂实现

可发现第二问实际要求的是 $2^p$ 那么我们可以使用分治的思路进行求解,也就是快速幂的方式进行快速幂的求解。

快速幂模板

//分治
int mypow(int a,int n){
    if(n==0) return 1;
    int t=mypow(a,n/2);
    if(n&1) return t*t*a;
    return t*t;
}
//倍增
int mypow(int a,int n){
    int ans=1;
    while(n){
        if(n&1) ans=ans*a;
        a=a*a;
        n>>=1;
    }
    return ans;
}

从模板中可发现只涉及到乘法的计算,结合本道题的数据范围,可以采用高精度乘法的方式进行处理。对于最后的减1,由于 $2^p$ ,p的值 $>1000$ 所以一定为偶数,减1必不可能导致退位所以,直接在高精度数字的最低位减1即可,不用加入高精度减法的计算。

计算过程中需要注意最终只需要保留最后500位,那么高精度乘法计算过程中,最多也只需要低500位参与计算即可。整体估算一下时间复杂度 ,高精度乘法部分一次计算最多为 $500^2$ ,快速幂部分复杂度为 $\log p$ ,整体为 $O(m\log p)$ ,m为数字位数,P为次幂数。根据本题数据规模 大致为 $10^6$的量级,必压位高精的速度更快。

代码实现

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e5 + 5;
struct node {
  int num[505];  // 高精度数值部分
  int len;       // 高精度数字位数
  friend node operator*(const node &A, const node &B) {
    // 重载* 计算高精度乘法  (模拟乘法竖式计算)
    node C = {0};
    int la = min(500, A.len), lb = min(500, B.len);
    for (int i = 0; i < la; i++) {
      for (int j = 0; j < lb; j++) {
        if (i + j > 500) continue;
        C.num[i + j] += A.num[i] * B.num[j];
        C.num[i + j + 1] += C.num[i + j] / 10;
        C.num[i + j] %= 10;
      }
    }
    C.len = min(500, la + lb);
    return C;
  }
};

// node mypow(node A, int p) {  // 倍增快速幂(高精度)
//   node ans = {{1}, 1};       // 1
//   while (p) {
//     if (p & 1) ans = ans * A;
//     A = A * A;
//     p >>= 1;
//   }
//   return ans;
// }

node mypow(node A, int p) {     // 分治快速幂(高精度)
  if (p == 0) return {{1}, 1};  // 2^0 = 1
  node t = mypow(A, p / 2);
  if (p & 1) return t * t * A;
  return t * t;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int p;
  cin >> p;
  // Q1: 位数
  cout << int(p * log10(2) + 1) << endl;
  // Q2: 2^p - 1
  node ans = mypow({{2}, 1}, p);  // 计算2^p
  ans.num[0]--;                   // 2^p - 1
  for (int i = 499; i >= 0; i--) {
    cout << ans.num[i];
    if (i % 50 == 0) cout << "\n";
  }
  return 0;
}
最后修改:2024 年 05 月 13 日
如果觉得我的文章对你有用,请随意赞赏