洛谷 P1045 【麦森数】快速幂

不用快速幂，压位出奇迹！

本人是个蒟蒻，不太熟悉快速幂，这里给大家介绍一种压位大法。

让我们来分析一下题目，第一位是送分的，有一个专门求位数的函数：n*log10(2)+1。 然后题目中p<=3100000,又要求后500位，普通算法肯定超时，但如果我们多压几位甚至时间都比普通快速幂少。而且我们用 long long 的话可以一次就乘上2的20次方又能节省时间；

第一问：

s=n*log10(2)+1;用函数算位数 
cout<<s<<endl;

第二问：算后500位：

while(n>=20){
        k=0;
        for(i=1;i<=50||i<=top;i++){//数组的每一个元素里放十位数 
            a[i]=a[i]*1048576+k;//每次乘上2的20次方：“1048576”把longlong剩余9位用到位 
            k=a[i]/ya;a[i]%=ya;//进位 
            if(top<50&&k&&i==top)top++;//加位数 
        }
        n-=20;//一次算20个 
    }

注意：n<20时还需要还需要用一次乘2的循环！

小于500位要加前导零：

while(i<=50){//小于500位，要加前导零 
            for(j=1;j<=5&&i<=50;i++,j++)cout<<"0000000000";//补10个0
            if(j==6)cout<<endl;
        }

大于500位的情况：

while(i>=1){//注意：大于五百位也有可能有前导零 
            for(j=1;j<=5&&i>=1;i--,j++){//是每一个元素（10位）中的的前导零
                if(a[i]>1000000000)cout<<a[i];//判断是否有前导零 
                else{
                    s=a[i];
                    while(s>0){s/=10;o++;}//记录前导零个数 
                    o=10-o;
                    while(o>0){o--;cout<<"0";}//输出 
                    cout<<a[i];
                }
            }
            cout<<endl;
        }

完整代码：（因为有些情况会重复，代码会有点长）

#include<iostream>
#include<cmath>
using namespace std;
long long a[51]={0,1},n,i,j,o,s,k,top=1;
int main(){
    cin>>n;
    s=n*log10(2)+1;//用函数算位数 
    cout<<s<<endl;
    while(n>=20){
        k=0;
        for(i=1;i<=50&&i<=top;i++){//数组的每一个元素里放十位数 
            a[i]=(a[i])<<20+k;//每次乘上2的20次方：1048576 把longlong剩余9位用到位 
            k=a[i]/10000000000;a[i]%=10000000000;//进位 
            if(top<50&&k&&i==top)top++;//加位数 ，前面s算过了 可以省 
        }
        n-=20;//一次算20个 
    }
    while(n){//把20个以下的依次算完 
        k=0;
        for(i=1;i<=50&&i<=top;i++){
            a[i]=a[i]<<1+k;
            k=a[i]/10000000000;a[i]%=10000000000;//用法同上 
            if(top<50&&k&&i==top)top++;
        }
        n--;
    }
    a[1]--;
    if(top<50){
        i=top+1;//可以用s 
        while(i<=50){//小于500位，要加前导零 
            for(j=1;j<=5&&i<=50;i++,j++)cout<<"0000000000";
            if(j==6)cout<<endl;
        }
        i=top;
        for(;j<=5&&i>=1;i--,j++){//注意：50位一行！！！j<=5!!! 
            if(a[i]>=1000000000)cout<<a[i];
            else{
                s=a[i];
                while(s>0){s/=10;o++;}
                o=10-o;
                while(o>0){o--;cout<<"0";}
                cout<<a[i];
            }
        }
        cout<<endl;
        while(i>=1){//注意：大于五百位也有可能有前导零 
            for(j=1;j<=5&&i>=1;i--,j++){//是每一个元素（10位）中的的前导零
                if(a[i]>1000000000)cout<<a[i];//判断是否有前导零 
                else{
                    s=a[i];
                    while(s>0){s/=10;o++;}//记录前导零个数 
                    o=10-o;
                    while(o>0){o--;cout<<"0";}//输出 
                    cout<<a[i];
                }
            }
            cout<<endl;
        }
    }
    else{
        s=a[50];
        i=50;
        while(i>=1){
            for(j=1;j<=5&&i>=1;i--,j++){
                if(a[i]>1000000000)cout<<a[i];
                else{
                    s=a[i];
                    while(s>0){s/=10;o++;}//      这一段用法同上 
                    o=10-o;
                    while(o>0){o--;cout<<"0";}
                    cout<<a[i];
                }
            }
            cout<<endl;
        }
    }
    return 0;
}

啊，好长啊，压位果然有副作用。

这是我的博客，发的题解和一些洛谷技巧都在里面。

另外，本人真的只是一个弱弱的萌新，7月份才入信息组，发的题解讨论等级不高，新人可看。