太经典的快速幂了

#include<bits/stdc++.h> using namespace std; const int N=500; int res[N]; void mul(int a[],int b[],int c[]){ int tmp[N]; memset(tmp,0,sizeof(tmp)); for(int i=0;i<N;i++) for(int j=0;j<N;j++) if(i+j<N) tmp[i+j]+=a[i]b[j]; for(int i=0,t=0;i<N;i++){ t+=tmp[i]; c[i]=t%10; t/=10; } } void quickpo(int p){ res[0]=1; int a[N]={2}; while(p){ if(p&1) mul(a,res,res); p>>=1; mul(a,a,a); } res[0]--; } int main(){ int p; cin>>p; cout<<int(plog10(2))+1<<endl; quickpo(p); for(int i=0,k=499;i<10;i++) for(int j=0;j<50;j++,k--) cout<<res[k]; return 0; }

#include<bits/stdc++.h> using namespace std; typedef vector<int> vi; const int N = 511; vi a(N),b(N); vi mul(vi x,vi y){ vi c(N2); for(int i=1;i<=510;i++){ for(int j = 1;j+i<=510;j++){ c[i+j-1] += x[i]y[j]; c[i+j]+=c[i+j-1]/10 ; c[i+j-1]%=10 ; } } return c; } int main(){ int p; cin>>p; int n = 2; a[1] = 2,b[1]=1; cout<<int(plog10(2))+1<<endl; while(p){ if(p%2) b= mul(a,b); a=mul(a,a); p/=2; } b[1]--; for(int i=10;i>=1;i--){ for(int j=0;j<50;j++){ printf("%d",b[i50-j]); } } return 0; }

#include<bits/stdc++.h> using namespace std; typedef vector<int> vi; const int N = 511; vi a(N),b(N); vi mul(vi x,vi y){ vi c(N2); for(int i=1;i<=510;i++){ for(int j = 1;j+i<=510;j++){ c[i+j-1] += x[i]y[j]; c[i+j]+=c[i+j-1]/10 ; c[i+j-1]%=10 ; } } return c; } int main(){ int p; cin>>p; int n = 2; a[1] = 2,b[1]=1; cout<<int(plog10(2))+1<<endl; while(p){ if(p%2) b= mul(a,b); a=mul(a,a); p/=2; } b[1]--; for(int i=10;i>=1;i--){ for(int j=0;j<50;j++){ printf("%d",b[i50-j]); } } return 0; }

#include<cstdio> #include<cmath> #include<cstring> using namespace std; int f[1001],p,res[1001],sav[1001];//乘法要开两倍长度 void result_1() { memset(sav,0,sizeof(sav)); for(register int i=1;i<=500;i+=1) for(register int j=1;j<=500;j+=1) sav[i+j-1]+=res[i]*f[j];//先计算每一位上的值（不进位） for(register int i=1;i<=500;i+=1) { sav[i+1]+=sav[i]/10;//单独处理进位问题，不容易出错 sav[i]%=10; } memcpy(res,sav,sizeof(res));//cstring库里的赋值函数，把sav的值赋给res } void result_2()//只是在result_1的基础上进行了细微的修改 { memset(sav,0,sizeof(sav)); for(register int i=1;i<=500;i+=1) for(register int j=1;j<=500;j+=1) sav[i+j-1]+=f[i]*f[j]; for(register int i=1;i<=500;i+=1) { sav[i+1]+=sav[i]/10; sav[i]%=10; } memcpy(f,sav,sizeof(f)); } int main() { scanf("%d",&p); printf("%d\n",(int)(log10(2)*p+1)); res[1]=1; f[1]=2;//高精度赋初值 while(p!=0)//快速幂模板 { if(p%21)result_1(); p/=2; result_2(); } res[1]-=1; for(register int i=500;i>=1;i-=1)//注意输出格式，50个换一行，第一个不用 if(i!=500&&i%500)printf("%d",res[i]); else printf("%d",res[i]); return 0; }