Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

ACAC

Posted by 40962501 at 2017-12-14 19:48:31 on Problem 1405 and last updated at 2017-12-14 19:49:13
/*
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator