麦森数


题目描述

洛谷(1045)

形如2^{P}-12P1的素数称为麦森数,这时PP一定也是个素数。但反过来不一定,即如果PP是个素数,2^{P}-12P1不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是P=3021377P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。

任务:从文件中输入PP(1000<P<31000001000<P<3100000),计算2^{P}-12P1的位数和最后500位数字(用十进制高精度数表示)

 

输入输出格式

输入格式:

文件中只包含一个整数PP(1000<P<31000001000<P<3100000)

输出格式:

第一行:十进制高精度数2^{P}-12P1的位数。

第2-11行:十进制高精度数2^{P}-12P1的最后500位数字。(每行输出50位,共输出10行,不足500位时高位补0)

不必验证2^{P}-12P1与PP是否为素数。

思路


弟弟思路

  1. 对于求位数,本质是 值/10  ,本文是2^p ,求出来明显不现实,但设置精度,比如 :

     1 int a=1,ans=0;
     2 while(p--){
     3     a*=2;
     4     if(a>10000000) {
     5         ++ans;
     6         a/=10;
     7     }
     8 }
     9 while(a){
    10     a/=10;
    11     ++ans;
    12 }

    当位数达到一定长度时,最后几位很难对位数再产生影响,只要  a>值 ,值 足够大就可以算出位数。

  2. 对于500位计算,分治法,如下:
     1  void work() {
     2      int c = 0, cl = 0;
     3      if (!flag &&p>0&& as[500] == 1)as[500] = 2;//没啥用,考虑初始p=0
     4      if (!flag)flag = 1;
     5      if (p == 0||p==1)return;
     6      else if (p % 2) {//p为奇数 ,拆分为 (p-1)/2+(p-1)/2+1
     7          --p;
     8         work();
     9         //处理函数
    10      }
    11     else { //p为偶数 拆为p/2,p/2
    12         p/=2;
    13         work();
    14         //处理函数
    15     }
    16 }
  3. 处理次方函数,如下:
     1 //yuan[]为最后要输出的数组,也为将要计算的数组,j为当前乘数的第j为在乘被乘数
     2 //jian[]乘数的第 (j-1) 位乘被乘数的结果,guo[]乘数的第 j 位乘被乘数的结果
     3 //is 为一表示 yuan[]*yuan[],处理p为偶数时平方降p(p/=2),否则cheng[]*yuan[],处理p为奇数时 k^[(p-1)/2+(p-1)/2] * k;
     4 void kk(int yuan[], int jian[], int guo[], int j, int is, int cheng[] = {}) {
     5     int flag = 0, c = 0, cl = 0;
     6     if (is) {
     7         for (int i = 500; i > 0; --i) {
     8             cl = yuan[i] * yuan[j] + jian[i + 1] + c;
     9             c = cl / 10;
    10             guo[i] = cl % 10;
    11         }
    12     }
    13     else {
    14         for (int i = 500; i > 0; --i) {
    15             cl = yuan[j] * cheng[i] + jian[i + 1] + c;
    16             c = cl / 10;
    17             guo[i] = cl % 10;
    18         }
    19     }
    20     if (j < 500)kk(yuan,guo, jian, j + 1,is, cheng);
    21     else for (int i = 0; i <= 503; ++i)yuan[i] = guo[i];
    22 }

自己的代码

#include<bits/stdc++.h> 
using namespace std;
int p, ans,flag;
int as[505],ccc[1010], ccb[1010];
void kk(int yuan[], int jian[], int guo[], int j, int is, int cheng[] = {}) {
    int flag = 0, c = 0, cl = 0;
    if (is) {
        for (int i = 500; i > 0; --i) {
            cl = yuan[i] * yuan[j] + jian[i + 1] + c;
            c = cl / 10;
            guo[i] = cl % 10;
        }
    }
    else {
        for (int i = 500; i > 0; --i) {
            cl = yuan[j] * cheng[i] + jian[i + 1] + c;
            c = cl / 10;
            guo[i] = cl % 10;
        }
    }
    if (j < 500)kk(yuan,guo, jian, j + 1,is, cheng);
    else for (int i = 0; i <= 503; ++i)yuan[i] = guo[i];
}

void work() {
    int c = 0, cl = 0;
    if (!flag &&p>0&& as[500] == 1)as[500] = 2;
    if (!flag)flag = 1;
    if (p == 0||p==1)return;
    else if (p % 2) {
        int zishen[505];
        for (int i = 0; i <= 503; ++i)zishen[i] = as[i];
        --p;work();
        memset(ccc, 0, sizeof(ccc));
        memset(ccb, 0, sizeof(ccb));
        kk(as, ccc, ccb, 1, 0,zishen);
    }
    else {
        c = 0, cl = 0;
        p /= 2;
        memset(ccc, 0, sizeof(ccc));
        memset(ccb, 0, sizeof(ccb));
        kk(as, ccc, ccb, 1, 1);
        work();
    }
}

int main() {
    scanf("%d", &p);
    as[500] = 1;
    int a = 1, ans = 0;
    while (p--) {
        a *= 2;
        if (a > 10000000) ++ans,a /= 10;    
    }
    while (a)  a /= 10;++ans;    
    work();
    for (int i = 500; i > 0; --i) {
        if (as[i] >0) { --as[i]; break; }
        else as[i] = 9;
    }
    printf("%d\n", ans);
    for (int i = 0; i < 10; ++i) {
        for (int j = 1; j <= 50; ++j) {
            printf("%d", as[i * 50 + j]);
        }
        printf("\n");
    }
    return 0;
}

 

大佬方法

  1. 对于位数,有函数在<cmath>中有log10(); 则 :ans = (p * log10(2) + 0.99);   搞定
  2. 对于500位计算,当我们对乘法列竖式时发现,乘数位数 j,被乘数位数 i ,每位乘出的数在同一列时,i+j 的和是相同的,代码来自(侵权删除):https://www.luogu.org/blog/28916/solution-p1045 
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    using namespace std;
    int f[1001],p,res[1001],sav[1001];//乘法要开两倍长度
    void result_1()
    {
        memset(sav,0,sizeof(sav));
        for(register int i=1;i<=500;i+=1)
            for(register int j=1;j<=500;j+=1)
                sav[i+j-1]+=res[i]*f[j];//先计算每一位上的值(不进位)
        for(register int i=1;i<=500;i+=1)
        {
            sav[i+1]+=sav[i]/10;//单独处理进位问题,不容易出错
            sav[i]%=10;
        }
        memcpy(res,sav,sizeof(res));//cstring库里的赋值函数,把sav的值赋给res
    }
    void result_2()//只是在result_1的基础上进行了细微的修改
    {
        memset(sav,0,sizeof(sav));
        for(register int i=1;i<=500;i+=1)
            for(register int j=1;j<=500;j+=1)
                sav[i+j-1]+=f[i]*f[j];
        for(register int i=1;i<=500;i+=1)
        {
            sav[i+1]+=sav[i]/10;
            sav[i]%=10;
        }
        memcpy(f,sav,sizeof(f));
    }
    int main()
    {
        scanf("%d",&p);
        printf("%d\n",(int)(log10(2)*p+1));
        res[1]=1;
        f[1]=2;//高精度赋初值
        while(p!=0)//快速幂模板
        {
            if(p%2==1)result_1();
            p/=2;
            result_2();
        }
        res[1]-=1;
        for(register int i=500;i>=1;i-=1)//注意输出格式,50个换一行,第一个不用
            if(i!=500&&i%50==0)printf("\n%d",res[i]);
            else printf("%d",res[i]);
        return 0;
    }

还是自己太菜了,没发现列竖式时,列相同 i+j 值相同

 


作者:洛绫璃,发布于:2019/07/11
原文:https://www.cnblogs.com/2aptx4869/p/11170009.html