题目链接

https://www.dotcpp.com/oj/problem1607.html

题目大意

计算2^p-1位数,及低500位数,输出。

解题思路

2的p次方,快速幂吧!
只不过快速幂中的乘,得换成高精度乘法了。
先看看快速幂的板子吧
还不知道啥是快速幂看看这个吧

ll ksm(ll x,ll t){//快速幂
     ll res=1;
     while(t>0){
          if(t&1LL) res=res*x%mod;
         t>>=1;
          x=x*x%mod;
    }
     return res;
}

类比一下,乘换成高精度,把取模操作去掉。

我的AC代码

直接对着代码讲吧,方便理解。
先整体看看,不看细节。
先看主函数高精度快速幂求出2^p,所谓高精度快速幂不过是把单精度加减乘除换成高精度的;
res--,求出的res的最低位要-1,求出2^p-1;
ceil,天花板的意思,就是取大于某数的最小整数。相对的,floor,地板,取小于某数的最大整数。重点是这个数学公式(根本没听说过),ceil(幂*log10(底数)) = 底数^幂 的位数;
输出。

函数讲解:
mul函数:高精度相乘,但是针对本题而言,因为我们只取低500位,因此,没必要用字符串存再转化,直接用数组存就行。这样一来,循环的终点都是500了,我们给全局数据res(即存最终答案的数组)赋值的时候,也是直接按着c的顺序赋值的,没必要反过来,反过来之后,再次进入相乘的时候,又要反过来计算,计算完了又反过来,可见,这是多此一举,所以,用res的低索引存低位。
x_mul函数:求x的平方,依然是只取低500位,与mul函数代码类似。

//我的代码 
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int res[N]={0,1},x[N]={0,2};//初始化不能忘!!忘掉爆炸!!
int c[N];

void mul(int* a,int* b){
    memset(c,0,sizeof c);//勿忘

    for(int i=1;i<=500;i++)//不管结果有多少位,我们只管最低500位,且低位的数值是不受高位影响的,但是高位的话会受到低位影响
        for(int j=1;j<=500;j++){//高精度乘法板子
            c[i+j-1]+=a[i]*b[j];
            c[i+j]+=c[i+j-1]/10;
            c[i+j-1]%=10;
        }

    for(int i=1;i<=500;i++)
        res[i]=c[i];//res与c数组相同的存储方式,小索引存低位    
}
void x_mul(){
    memset(c,0,sizeof c);//勿忘

    for(int i=1;i<=500;i++)
        for(int j=1;j<=500;j++){
            c[i+j-1]+=x[i]*x[j];
            c[i+j]+=c[i+j-1]/10;
            c[i+j-1]%=10;
        }

    for(int i=1;i<=500;i++)
        x[i]=c[i];
}
int main(){
    int p;
    cin>>p;
    int tmp=p;
        //快速幂变形而已
     while(tmp>0){
          if(tmp&1) mul(res,x);
         tmp>>=1;
          x_mul();
    }
    res[1]--;//求出的res的最低位要-1,因为要求2^p-1
    //为什么直接最低位-1就行,万一个位数是0呢?
        //其实,根本不存在个位为0的情况,至少也是2,因为2^1=2,无论乘多少个2,个位显然都不会变成0吧,除非乘0,所以你可以放心地进行-1;
    cout<<ceil(p*log10(2));//ceil函数+数学公式

    for(int i=500;i>=1;i--){//输出
        if((i)%50==0) cout<<endl;
        cout<<res[i];        
    }    
} 

大佬的AC代码

本质没变,还是高精度快速幂。
大佬有三个函数,pow_2函数:高精度平方函数,mul_2函数:高精度乘2函数,get_res函数:快速幂函数。
get_res函数:
递归调用自己,若幂/2不为1,继续递归调用自己,参数为n/2;
进行平方操作;
若x为奇数,将结果进行乘2操作。
(不是很会讲,你可以举几个例子试试,你可以理解为一个木棒,不停地截取一半,要是能正好分一半,就平方,没法正好分一半,就平方后再乘上2)
pow_2函数:
类板子,求平方,取低500位。
mul_2函数:
类板子,*2操作,取低500位。

#include<bits/stdc++.h>
using namespace std;
const int N=1200;
int res[N];
int p;
void pow_2(){
    int c[N];
    memset(c,0,sizeof c);

    for(int i=1;i<=500;i++)    
        for(int j=1;j<=500;j++)
            c[i+j-1]+=res[i]*res[j];
    for(int i=1;i<=500;i++){
        c[i+1]+=c[i]/10;
        c[i]%=10;
    }

    for(int i=1;i<=500;i++)
        res[i]=c[i];
}
void mul_2(){
    int c[N];
    memset(c,0,sizeof c);

    for(int i=1;i<=500;i++)
        res[i]*=2;
    for(int i=1;i<=500;i++){
        res[i+1]+=res[i]/10;
        res[i]%=10;
    }

}
void get_res(int x){
    if(x/2!=1) get_res(x/2);
    pow_2();
    if(x%2==1) mul_2();
}
int main(){
    cin>>p;
    cout<<ceil(p*log10(2));

    res[1]=2;
    get_res(p);
    res[1]--;

    for(int i=500;i>=1;i--){
        if(i%50==0) cout<<endl;
        cout<<res[i];
    }
}

二者区别

我的代码:
图片说明
大佬代码:
图片说明
“正确”后的两个数依次是“内存”和“耗时”。

总结

尽管知道是高精度快速幂,但是还是没实现出来,最后还是仿照大佬的代码去实现了一遍。
重点记忆:
ceil(幂*log10(底数)) 为底数^幂的位数
不同的快速幂板子。