麦森数

2024-01-14 13:03:10

题目描述

洛谷（1045）

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

任务：从文件中输入PP（1000<P<31000001000<P<3100000），计算2^{P}-12P−1的位数和最后500位数字（用十进制高精度数表示）

输入输出格式

输入格式：

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

输出格式：

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

第2-11行：十进制高精度数2^{P}-12P−1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）

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

思路

弟弟思路

对于求位数，本质是值/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>值，值足够大就可以算出位数。

对于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 }

处理次方函数，如下：

 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;
}

大佬方法

对于位数，有函数在<cmath>中有log10（）；则：ans = (p * log10(2) + 0.99); 搞定

对于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 值相同

码农公寓

题目描述

输入输出格式

思路

相关文章