/*
高精度類
包含加法和乘法，
乘法未用FFT優化。
只能應對數據不斷增加的正整數
by hplonline
*/
#include "bigint.h"
#include "string.h"
#include "stdio.h"
#include "math.h"

int round(double db){
	int a = int(db) ;
	if ( db - a >= 0.5 ) return a + 1 ;
	else return a ;
}

bool CBigInt::operator==(CBigInt &bi){
	int i ;
	if ( l != bi.l ) return false ;
	for ( i = 0 ; i < l ; i ++ ) if ( data[i] != bi.data[i] ) return false ;
	return true ;
}

const int MAXFL = 2 * MAXL ;

//can be allocated in mul_fft function 
complex a[MAXFL] , b[MAXFL] ;

CBigInt& CBigInt::mul_fft(CBigInt &bi){
	//here may need new and delete
	int *c ;
	int i , m ; 
	for ( i = 0 ; i < l ; i ++ ){
		a[i].real = data[i] ;
		a[i].imag = 0 ;
	}
	for ( i = 0 ; i < bi.l ; i ++ ){
		b[i].real = bi.data[i] ;
		b[i].imag = 0 ;
	}
	m = 1 ;
	while ( m < l || m < bi.l ) m <<= 1 ;
	m <<= 1 ;

	for ( i = l ; i < m ; i ++ ) {
		a[i].real = 0 ;
		a[i].imag = 0 ;
	}

	for ( i = bi.l ; i < m ; i ++ ){
		b[i].real = 0 ;
		b[i].imag = 0 ;
	}
	fr.fft( a , m ) ;
	fr.fft( b , m ) ;
	for ( i = 0 ; i < m ; i ++ ) a[i] *= b[i] ;

	fr.ifft( a , m ) ;
	
	c = (int*) b ;
	memset( c , 0 , sizeof(int) * MAXL ) ;
	for ( i = 0 ; i < m ; i ++ ) c[i] = round ( a[i].real ) ;
	for ( i = 0 ; i < m - 1 ; i ++ ) {
		c[i + 1] += c[i] / 10 ;
		c[i] %= 10 ;
	}
	for ( i = m - 1 ; i >= 0 ; i -- )if ( c[i] != 0 ) break; 
	l = i + 1 ;
	for ( i = 0 ; i < l ; i ++ ) data[i] = c[i] ;
	return *this ;
}

void CBigInt::init(int i){
	l = 0 ;
	memset(data,0,sizeof(data)) ;
	do{
		data[l] = i % 10 ;
		i /= 10 ;
		l ++ ;
	}while(i);
}

void CBigInt::clear(){
	l = 1 ;
	memset(data,0,sizeof(data)) ;
}

CBigInt::CBigInt(){
	clear();
}

CBigInt::CBigInt(int i){
	init(i);
}

CBigInt::CBigInt(CBigInt &bi){
	memset(data,0,sizeof(data));
	int i ;
	l = bi.l ;
	for ( i = 0 ; i < l ; i ++ ) data[i] = bi.data[i] ;
}

CBigInt& CBigInt::add(CBigInt &bi){
	int i = 0 ; 
	int p = 0 ;
	while ( i < l || i < bi.l ){
		p += data[i] + bi.data[i] ;
		data[i] = p % 10 ;
		p /= 10 ;
		i ++ ;
	}
	if ( p ) {
		data[i] = p ;
		i ++ ;
	}
	l = i ;
	return *this ;
}

CBigInt& CBigInt::mul(CBigInt &bi){
	int tmp[MAXL] ;
	int i , j , p ;
	memset(tmp,0,sizeof(tmp)) ;
	for ( i = 0 ; i < l ; i ++ ){
		for ( j = 0 ; j < bi.l ;j ++ ){
			tmp[i + j] += data[i] * bi.data[j] ;
		}
	}
	j = l + bi.l + 1;
	p = 0 ;
	for ( i = 0 ; i < j ; i ++ ){
		p += tmp[i] ;
		data[i] = p % 10 ;
		p /= 10 ;
	}
	if ( p ){
		data[i] = p ;
		i ++ ;
	}
	while ( !data[i] ) i -- ;
	l = i + 1 ;
	return *this ;
}

CBigInt& CBigInt::operator+(CBigInt &bi){
	CBigInt *p = new CBigInt(*this) ;
	return p->add(bi) ;
}

CBigInt& CBigInt::operator*(CBigInt &bi){
	CBigInt *p = new CBigInt(*this) ;
	return p->mul(bi);
}

CBigInt& CBigInt::operator+=(CBigInt &bi){
	add(bi);
	return *this ;
}

CBigInt& CBigInt::operator*=(CBigInt &bi){
	mul(bi);
	return *this ;
}

CBigInt& CBigInt::operator=(CBigInt &bi){
	int i;
	memset(data,0,sizeof(data));
	l = bi.l ;
	for ( i = 0 ; i < l ; i ++ ) data[i] = bi.data[i] ;
	return *this ;
}

void CBigInt::output(){
	int i;
	for ( i = l - 1 ; i >= 0 ; i -- ) printf("%d",data[i]) ;
	//for ( i = l - 1 ; i >= 0 ; i -- )putchar('0' + data[i]);
}