P1045[NOIP 2003 普及组]麦森数题解

题目描述

输入

P(1000<P<3.1 \times 10^5)

。

计算

2^{P}-1

的位数和最后

500

位数字（用十进制高精度数表示）。

题目分析

这道题要用到高精度和快速幂。

本题要求计算

2^P(P \le 3.1 \times 10^5)

的最后

t ( t = 500 )

位，必然要用到高精度，用数组来存储每一位的值，我们将

k_1

定义为

2^P

在十进制中的位数。

如果用普通高精度思路直接运算来做，会超时，时间复杂度达到了

O(P \times \log ( k_1))

。

通过

2^P

就想到了快速幂（二进制取幂）来优化。

快速幂主要思路：

\textstyle a ^ {2 \times b + 1} = a^ {2 \times b} \times a

\textstyle a ^ {2 \times b} = a ^ b \times a ^ b

定义

f

数组用于存储当前需要平方的基数，初始值为

2

，表示

2^ 1 =2

。

l

数组用于存储累积计算结果，保存

2^P

的高精度值，初始值为

1

，

f_1

表示个位，

f_2

表示十位，以此类推。

用循环从末尾往前位实现，在二进制中，最后一位若为

1

，则乘上该位所对应的二次幂的值，即执行

l = l \times f

。

f

每次循环

\times 2

。

举例：

P=5

（二进制

101

）时：

第一次循环： $P=5$ （末位 $1$ ）， $l= 1 \times 2 =2$ ， $f= 2 ^ 2 =4$ ， $P=2$ 。
第一次循环： $P=2$ （末位 $0$ ）， $f= 4 ^ 2 =16$ ， $P=1$ 。
第三次循环： $P=1$ （末位 $1$ ）， $l= 2 \times 16 =32$ ， $f= 16 ^ 2 =256$ ， $P=0$ 。

最终结果：

2^ 5 =32

。

我们将

k_2

定义为

P

在二进制中的位数，这时时间复杂度为

O(k_2 \times t^2)

。

题目代码

超详细注释代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int p;
int f[1005],l[1005];
int s[1005];//用于存储高精度乘法的中间计算
//函数s1：计算 l=l*f（结果乘以当前基数）
void s1(){
    memset(s,0,sizeof(s));//清空临时数组
    for(int i=1;i<=500;i++){
        for(int j=1;j<=500;j++){
            s[i+j-1]+=l[i]*f[j];//l的每一位乘以f的每一位
        }
    }
    //处理进位
    for(int i=1;i<=500;i++){
        s[i+1]+=s[i]/10;//进位到高位
        s[i]%=10;//当前位保留个位数
    }
    memcpy(l,s,sizeof(l));//将结果复制回l数组
}
//函数s2：计算f=f*f（基数平方），方法同函数s1
void s2(){
    memset(s,0,sizeof(s));
    for(int i=1;i<=500;i++){
        for(int j=1;j<=500;j++){
            s[i+j-1]+=f[i]*f[j];
        }
    }
    for(int i=1;i<=500;i++){
        s[i+1]+=s[i]/10;
        s[i]%=10;
    }
    memcpy(f,s,sizeof(f));
}
int main(){
    cin>>p;
    //计算2^P-1的位数公式：log10(2^P)=P*log10(2)，加1得到位数
    cout<<(int)(log10(2)*p+1);
    l[1]=1;
    f[1]=2;
    //通过二进制分解P
    while(p!=0){
        if(p%2==1){
            s1();
        }
        p/=2;//去掉p二进制中的最后一位
        s2();
    }
    //直接对个位减1，因为末尾只可能是2，4，6，8
    l[1]-=1;
    //输出需从高位到低位输出，因为逆序存储
    for(int i=500;i>=1;i--) {
        if(i%50==0)cout<<"\n";//每50位换行
        cout<<l[i];
    }
    return 0;
}

无注释放心食用代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int p,f[1005],l[1005],s[1005];
void s1(){
    for(int i=1;i<=500;i++){
        for(int j=1;j<=500;j++){
            s[i+j-1]+=l[i]*f[j];
        }
    }
    for(int i=1;i<=500;i++){
        s[i+1]+=s[i]/10;
        s[i]%=10;
    }
    memcpy(l,s,sizeof(l));
}
void s2(){
    memset(s,0,sizeof(s));
    for(int i=1;i<=500;i++){
        for(int j=1;j<=500;j++){
            s[i+j-1]+=f[i]*f[j];
        }
    }
    for(int i=1;i<=500;i++){
        s[i+1]+=s[i]/10;
        s[i]%=10;
    }
    memcpy(f,s,sizeof(f));
}
int main(){
    cin>>p;
    cout<<(int)(log10(2)*p+1);
    l[1]=1;
    f[1]=2;
    while(p!=0){
        if(p%2==1){
            memset(s,0,sizeof(s));
            s1();
        }
        p/=2;
        s2();
    }
    l[1]-=1;
    for(int i=500;i>=1;i--) {
        if(i%50==0)cout<<"\n";
        cout<<l[i];
    }
    return 0;
}

压缩版代码：

CPP

#include<bits/stdc++.h>
using namespace std;int p,f[1005],l[1005],s[1005];int main(){cin>>p;cout<<(int)(log10(2)*p+1);l[1]=1;f[1]=2;while(p!=0){if(p%2==1){memset(s,0,sizeof(s));for(int i=1;i<=500;i++){for(int j=1;j<=500;j++){s[i+j-1]+=l[i]*f[j];}}for(int i=1;i<=500;i++){s[i+1]+=s[i]/10;s[i]%=10;}memcpy(l,s,sizeof(l));}p/=2;memset(s,0,sizeof(s));for(int i=1;i<=500;i++){for(int j=1;j<=500;j++){s[i+j-1]+=f[i]*f[j];}}for(int i=1;i<=500;i++){s[i+1]+=s[i]/10;s[i]%=10;}memcpy(f,s,sizeof(f));}l[1]-=1;for(int i=500;i>=1;i--){if(i%50==0)cout<<"\n";cout<<l[i];}}

题解：P1045 [NOIP 2003 普及组] 麦森数

文章操作