Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
ACAC/* username:40962501 */ #include<iostream> #include<stdio.h> using namespace std; const int BASE=1000000000; const int MAXD=8592; struct BigPosInt{ __int64 d[MAXD]; int n; }; void InitBpi(BigPosInt &bpi); void PrintBpi(BigPosInt &bpi); void Inc(BigPosInt &bpi); void Dec(BigPosInt &bpi); void Multiply(const BigPosInt &bpi1,const BigPosInt &bpi2, BigPosInt &bpi3); int main(){ int N; BigPosInt ans; BigPosInt bpi1,bpi2; int i; scanf("%d",&N); printf("2\n");N--; InitBpi(bpi1); bpi1.d[0]=2;bpi1.n=1; while(N-->0){ InitBpi(ans); bpi2.n=bpi1.n; for(int i=0;i<bpi1.n;i++){ bpi2.d[i]=bpi1.d[i]; } Dec(bpi2);Multiply(bpi1,bpi2,ans); Inc(ans); PrintBpi(ans); bpi1.n=ans.n; for(int i=0;i<ans.n;i++){ bpi1.d[i]=ans.d[i]; } } return 0; } void InitBpi(BigPosInt &bpi){ for(int i=0;i<MAXD;i++){ bpi.d[i]=0; } bpi.n=0; } void PrintBpi(BigPosInt &bpi){ if(bpi.n<=0) return ; int i; printf("%I64d",bpi.d[bpi.n-1]); for(i=bpi.n-2;i>=0;i--){ if(bpi.d[i]<100000000){ printf("%.9I64d",bpi.d[i]); } else { printf("%I64d",bpi.d[i]); } } printf("\n"); } void Inc(BigPosInt &bpi){ int i; bpi.d[0]++; for(i=0;i<bpi.n;i++){ if(bpi.d[i]>=BASE){ bpi.d[i]-=BASE; bpi.d[i+1]++; } else break; } if(bpi.d[bpi.n]!=0){ bpi.n++; } } void Dec(BigPosInt &bpi){ int i; bpi.d[0]--; for(i=0;i<bpi.n;i++){ if(bpi.d[i]<0){ bpi.d[i]+=BASE; bpi.d[i+1]--; } else break; } if(bpi.d[bpi.n-1]==0){ bpi.n--; } } void Multiply(const BigPosInt &bpi1,const BigPosInt &bpi2, BigPosInt &bpi3){ int i,j; InitBpi(bpi3); for(i=0;i<bpi1.n;i++){ for(j=0;j<bpi2.n;j++){ bpi3.d[i+j]+=bpi1.d[i]*bpi2.d[j]; bpi3.d[i+j+1]+=bpi3.d[i+j]/BASE; bpi3.d[i+j]%=BASE; } } for(i=bpi1.n+bpi2.n+10;i>=0;i--){ if(bpi3.d[i]!=0){ bpi3.n=i+1; break; } } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator