P1045 麦森数题解

Mindulle · 2025-06-02 20:41:09 · 题解

首先，我们来思考如何计算 2^p-1 的位数，由于 2^p 的个位不可能是 0，故 2^p-1 与 2^p 的位数必然是相同的。

设 2^p 的位数为 k，则有不等式：

10^k>2^p>10^{k-1}

变形可以得到：

k>\log_{10}{2^p}>k-1

根据对数的运算法则又可以进行一次变形：

k>p×\log_{10}{2}>k-1

故其位数为 [p×\log_{10}{2}+1]，其中 [x] 为不超过 x 的最大整数。

可以使用库函数：

log10(x)

接下来考虑如何计算 2^p-1 的后 500 位，p 很大，我想到了快速幂和高精度乘法来解决，下面是基础的快速幂。

大家都知道，对于 a^b：

若 b 是偶数，有 a^b=(a^{\frac {b} {2}})^2。 \ 若 b 是奇数，有 a^b=(a^{\frac {b-1} {2}})^2 × a。

那么我们就可以写出：

//这里是计算a的b次方对mod取余的结果。
long long quick_pow(long long a,long long b,long long mod){
    long long res=1; //因为是幂运算，res要是1不能是0
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

因为是高精度，所以这里有几个地方要修改，修改过后的代码：

void quick_pow(int p){
    res[0]=1,a[0]=2;
    while(p){
        if(p&1) multiply1(); //高精度乘法1
        multiply2(); //高精度乘法2
        p>>=1;
    }
}

这个问题就完美地解决了。最后需要注意是 50 个为一行。

Code

#include<bits/stdc++.h>
int n,a[1010],res[1010],cnt;
void multiply1(){ //高精度乘法模板1
    int tmp[1010]={0};
    for(int i=0;i<500;i++){
        for(int j=0;j<500;j++) tmp[i+j]+=res[i]*a[j];
    }
    int t=0;
    for(int i=0;i<500;i++){
        tmp[i]+=t;
        res[i]=tmp[i]%10;
        t=tmp[i]/10;
    }
}
void multiply2(){ //高精度乘法模板2
    int tmp[1010]={0};
    for(int i=0;i<500;i++){
        for(int j=0;j<500;j++) tmp[i+j]+=a[i]*a[j];
    }
    int t=0;
    for(int i=0;i<500;i++){
        tmp[i]+=t;
        a[i]=tmp[i]%10;
        t=tmp[i]/10;
    }
}
void quick_pow(int p){ //快速幂
    res[0]=1,a[0]=2;
    while(p){
        if(p&1) multiply1();
        multiply2();
        p>>=1;
    }
}
int main(){
    scanf("%d",&n);
    int length=n*log10(2)+1;
    printf("%d\n",length);
    quick_pow(n);
    res[0]-=1; //为什么能减1？因为不可能退位
    for(int i=499;i>=0;i--){
        if(cnt==50) printf("\n"),cnt=0; //每50个要记得换行
        printf("%d",res[i]);
        cnt++;
    }
    return 0;
}

P1045 麦森数 题解

P1045 麦森数题解