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

· · 题解

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）时：

  1. 第一次循环：P=5（末位 1），l= 1 \times 2 =2，f= 2 ^ 2 =4，P=2。

  2. 第一次循环：P=2（末位 0），f= 4 ^ 2 =16，P=1。

  3. 第三次循环：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)。

题目代码

超详细注释代码：

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

无注释放心食用代码：

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

压缩版代码：

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

写题解不易，记得点个赞再走吧。