xingshucheng @ 2020-04-17 22:52:38
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef char gao[100005];
typedef int big[100005];big a,b,w,c,tmp;
inline void jian(gao &z,gao x,gao y)
{
int lena,lenb,len,m=0,s=0,q=0;
memset(a,0,sizeof(a));memset(b,0,sizeof(b));
memset(c,0,sizeof(c));memset(w,0,sizeof(w));
lena=strlen(x);lenb=strlen(y);
for(register int i=0;i<lena;++i)a[lena-i]=x[i]-48;
for(register int i=0;i<lenb;++i)b[lenb-i]=y[i]-48;
len=max(lena,lenb);
for(register int i=1;i<=len;++i)
{c[i]+=a[i]-b[i];if(c[i]<0){c[i]+=10;c[i+1]--;}}
while(c[len]==0&&len>1)--len;m=c[len];
for(int i=len;i>=1;--i){++s;w[s]=c[i];}
for(int i=len;i>=1;--i)c[i]=w[i];
if (len-1>=1)q=len;else q=1;
memset(z,0,sizeof(z));
for(register int i=0;i<q;++i)
z[i]=c[i+1]+'0';return;
}
inline void jia(gao &z,gao x,gao y)
{
int lena,lenb,len,m=0,s=0,q=0;
memset(a,0,sizeof(a));memset(b,0,sizeof(b));
memset(c,0,sizeof(c));memset(w,0,sizeof(w));
lena=strlen(x);lenb=strlen(y);
for(register int i=0;i<lena;++i)a[lena-i]=x[i]-48;
for(register int i=0;i<lenb;++i)b[lenb-i]=y[i]-48;
len=max(lena,lenb);for(register int i=1;i<=len;++i)
{c[i+1]=(c[i]+a[i]+b[i])/10;c[i]=(c[i]+b[i]+a[i])%10;}
if(c[len+1]>0)++len;while(c[len]==0&&len>1)--len;
for(register int i=len;i>=1;--i){++s;w[s]=c[i];}
for(register int i=len;i>=1;--i)
c[i]=w[i];if(len-1>=1)q=len;else q=1;
for(register int i=0;i<q;++i)
z[i]=c[i+1]+'0';return;
}
inline int maxx(int x,int y)
{if(x>y)return x;else return y;}
inline void sub(big &a,big &b,int &lena,int &lenb)
{
for(register int i=1;i<=lena;++i)
{
a[i]=a[i]-b[i];
if(a[i]<0){a[i]+=10;--a[i+1];}
}
while(a[lena]==0&&lena>1)--lena;
return;
}
inline int comp(big &a,big &b,int &lena,int &lenb)
{
long long up=maxx(lena,lenb);
for(register int i=lena+1;i<=up;++i)a[i]=0;
for(register int i=lenb+1;i<=up;++i)b[i]=0;
for(register int i=0;i<up;i++)
{
if(a[up-i]>b[up-i])return 1;
if(a[up-i]<b[up-i])return -1;
}
return 0;
}
inline void joint(big &p,big &q,int det,int lena)
{
for(register int i=1;i<=lena;++i)
q[i+det-1]=p[i];q[0]=lena+det-1;
return;
}
inline void chufa(gao &aa,gao s1,gao s2)
{
int lena,lenb,lenc,s=-1;
memset(tmp,0,sizeof(tmp));
memset(aa,0,sizeof(aa));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
lena=strlen(s1);lenb=strlen(s2);lenc=lena-lenb+1;
for(register int i=0;i<lena;++i)
a[i+1]=s1[lena-i-1]-'0';
for(register int i=0;i<lenb;++i)
b[i+1]=s2[lenb-i-1]-'0';
for(register int i=lenc;i>=1;--i)
{
memset(tmp,0,sizeof(tmp));
joint(b,tmp,i,lena);
while(comp(a,tmp,lena,tmp[0])>=0)
{sub(a,tmp,lena,tmp[0]);++c[i];}
}
while(c[lenc]==0&&lenc>1)--lenc;
if(lenc<1)c[lenc=1]=0;
for(register int i=lenc;i>=1;--i)
aa[lenc-1-(++s)]=c[lenc-i+1]+'0';
return;
}
inline void cheng(gao &z,gao x,gao y)
{
int lena,lenb,len,m=0,s=0,q=0;
memset(a,0,sizeof(a));memset(b,0,sizeof(b));
memset(c,0,sizeof(c));memset(w,0,sizeof(w));
lena=strlen(x);lenb=strlen(y);
for(register int i=0;i<lena;++i)a[lena-i]=x[i]-48;
for(register int i=0;i<lenb;++i)b[lenb-i]=y[i]-48;
for(register int i=1;i<=lena;++i)
for(register int j=1;j<=lenb;++j)
c[i+j-1]+=a[i]*b[j];len=lena+lenb;
for(register int i=1;i<=len;++i)
{c[i+1]+=c[i]/10;c[i]%=10;}
while(c[len]==0&&len>1)--len;m=c[len];
while(m>0){c[len]=m%10;m/=10;++len;}
for(register int i=len-1;i>=1;--i){++s;w[s]=c[i];}
for(register int i=len-1;i>=1;--i)
c[i]=w[i];if(len-1>1)q=len-1;else q=1;
for(register int i=0;i<q;++i)
z[i]=c[i+1]+'0';return;
}
inline void qumo(gao &z,gao x,gao y)
{
gao a,b;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(z,0,sizeof(z));
chufa(a,x,y);
cheng(b,y,a);
jian(z,x,b);
return;
}
inline void hhs(gao &x,int y)
{
gao k;int s=0;
while(y!=0){k[s++]=y%10+'0';y/=10;}
memset(x,0,sizeof(x));
for(register int i=0;i<s;i++)x[i]=k[s-i-1];
return;
}
inline void ksm(gao &x,gao y,gao b)
{
gao ans,m,t,z,k;strcpy(z,b);
memset(ans,0,sizeof(ans));
memset(m,0,sizeof(m));
memset(t,0,sizeof(t));
strcpy(m,y);
strcpy(ans,"1");
memset(x,0,sizeof(x));
while(strcmp(z,"0")!=0)
{
hhs(k,2);
qumo(t,z,k);
if(strcmp(t,"0")!=0)
cheng(ans,ans,m);
cheng(m,m,m);
chufa(t,z,k);
strcpy(z,t);
}
strcpy(x,ans);
return;
}
inline void read(int &x)
{
x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
x*=f;return;
}
inline void write(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');return;
}
int main()
{
gao sum,k,q,d;int p;read(p);hhs(d,p);
strcpy(sum,"0");strcpy(k,"2");strcpy(q,"1");
ksm(sum,k,d);jian(sum,sum,q);
write(strlen(sum));puts("");
// printf("%s",sum);return 0;
if(strlen(sum)>=500)
{
int s=0;
for(register int i=0;i<=499;++i)
{
putchar(sum[strlen(sum)-500+i]);
s++;if(s==50){puts("");s=0;}
}
}else
{
int s=0;
for(register int i=0;i<=499-strlen(sum);++i)
{
putchar('0');s++;if(s==50){puts("");s=0;}
}
for(register int i=0;i<=499;++i)
{
putchar(sum[i]);
s++;if(s==50){puts("");s=0;}
}
}
return 0;
}by Shallow_sing @ 2020-04-17 23:13:53
就是普通的高精乘
#include<bits/stdc++.h>
using namespace std;
const int n=500;
int a[1010],c[1010];
int t[1010];
void chengfa(int ta[],int tb[],int tc[]){
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
t[i+j-1]+=ta[i]*tb[j];
}
}
for(int i=1;i<=n;i++){
t[i+1]+=t[i]/10;
t[i]%=10;
}
for(int i=1;i<=n;i++){
tc[i]=t[i];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int p;
cin>>p;
cout<<int(log10(2)*p)+1<<endl;
a[1]=2,c[1]=1;
while(p){
if(p%2==1)chengfa(a,c,c);
p/=2;
chengfa(a,a,a);
}
c[1]--;
int tmp=0;
for(int i=n;i>=1;i--){
tmp++;
cout<<c[i];
if(tmp==50){
tmp=0;
cout<<endl;
}
}
return 0;
}by xingshucheng @ 2020-04-18 07:08:45
谢谢
by justinjia @ 2021-02-05 13:38:19
@xingshucheng 现在不是禁止#pragma吗？