自动搬运

查看原文

来自洛谷，原作者为

	Mindulle 目前活跃系统：2513 剑鱼（Kajiki），强度：14级（45m/s）

搬运于2025-08-24 21:20:17，当前版本为作者最后更新于2025-06-02 20:41:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

变形可以得到：

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

故其位数为 $[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;
}