https://www.luogu.org/problemnew/show/P1045

第一问：2^p-1的位数，就是log10(2^p-1)+1向下取整

第二问：(2^p-1)%(10^500).需要用高精度快速幂，暴力会超时。

保留后500位在高精度里实现就好了。

快速幂非递归：利用     若b是偶数，a^b=(a^2)^(b/2) ；若b是奇数，a^b=(a^2)^(b/2)*a

#include<bits/stdc++.h>
using namespace std;
const int L=10005;


string mul(string a,string b)//a,b均为非负整数
{
    string s;
    int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();//na存储被乘数，nb存储乘数，nc存储积
    fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);//将na,nb,nc都置为0
    for(int i=La-1;i>=0;i--) na[La-1-i]=a[i]-'0';//将字符串表示的大整形数转成i整形数组表示的大整形数
    for(int i=Lb-1;i>=0;i--) nb[Lb-1-i]=b[i]-'0';
    for(int i=0;i<La;i++)
        for(int j=0;j<Lb;j++)
            nc[i+j]+=na[i]*nb[j];//a的第i位乘以b的第j位为积的第i+j位（先不考虑进位）
    for(int i=0;i<La+Lb-1;i++)
        nc[i+1]+=nc[i]/10,nc[i]%=10;//统一处理进位
    int pos=La+Lb;
    while((!nc[--pos])&&pos)continue; 
    pos++;
    for(int i=pos-1;i>=0;i--)
        s+=nc[i]+'0';//将整形数组转成字符串
    if(s.length()<=500)return s;
    return s.substr(s.length()-500);
}

int main()
{
    int p;cin>>p;
    cout<<(int)(p*log10(2)+1)<<"\n";
    string a="2",ans="1";
    while(p)
    {
        if(p&1)ans=mul(ans,a);
        p>>=1;
        a=mul(a,a);
    }
    string ans2;
    int len2=500-ans.length();
    for(int i=0;i<len2;i++)ans2+='0';
    if(ans.length()<500)ans=ans2+ans;
    ans[499]=ans[499]-1;
    for(int i=0;i<10;i++)
        cout<<ans.substr(i*50,50)<<"\n";
    return 0;
}

快速幂递归：

#include<bits/stdc++.h>
using namespace std;
const int L=10005;


string mul(string a,string b)//a,b均为非负整数
{
    string s;
    int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();//na存储被乘数，nb存储乘数，nc存储积
    fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);//将na,nb,nc都置为0
    for(int i=La-1;i>=0;i--) na[La-1-i]=a[i]-'0';//将字符串表示的大整形数转成i整形数组表示的大整形数
    for(int i=Lb-1;i>=0;i--) nb[Lb-1-i]=b[i]-'0';
    for(int i=0;i<La;i++)
        for(int j=0;j<Lb;j++)
            nc[i+j]+=na[i]*nb[j];//a的第i位乘以b的第j位为积的第i+j位（先不考虑进位）
    for(int i=0;i<La+Lb-1;i++)
        nc[i+1]+=nc[i]/10,nc[i]%=10;//统一处理进位
    int pos=La+Lb;
    while((!nc[--pos])&&pos)continue; 
    pos++;
    for(int i=pos-1;i>=0;i--)
        s+=nc[i]+'0';//将整形数组转成字符串
    if(s.length()<=500)return s;
    return s.substr(s.length()-500);
}
string mul(string a,int b)//高精度a乘单精度b
{
    int na[L];
    string ans;
    int La=a.size();
    fill(na,na+L,0);
    for(int i=La-1;i>=0;i--) na[La-i-1]=a[i]-'0';
    for(int i=0;i<La;i++) na[i]=na[i]*b;    
    int pos;
    for(pos=0;pos<La-1;pos++)na[pos+1]+=na[pos]/10,na[pos]%=10;
    while(na[pos])na[pos+1]=na[pos]/10,na[pos]%=10,pos++;
    while((!na[--pos])&&pos)continue; 
    pos++;
    for(int i=pos-1;i>=0;i--)ans+=na[i]+'0';
    if(ans.length()<=500)return ans;
    return ans.substr(ans.length()-500);
}
string mod(int a,int n)
{
    if(n==0)return "1";
    string ans=mod(a,n/2);
    ans=mul(ans,ans);
    if(n&1)ans=mul(ans,a);
    return ans; 
}

int main()
{
    int p;cin>>p;
    cout<<(int)(p*log10(2)+1)<<"\n";
    string a="2",ans="1";
    ans=mod(2,p);
    string ans2;
    int len2=500-ans.length();
    for(int i=0;i<len2;i++)ans2+='0';
    if(ans.length()<500)ans=ans2+ans;
    ans[499]=ans[499]-1;
    for(int i=0;i<10;i++)
        cout<<ans.substr(i*50,50)<<"\n";
    return 0;
}