#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<string>

#include "Numero.hpp"

Numero::Numero(const char* n)
{
	nd= strlen(n);
	dig= new char[nd];
	for (int i=0, k=nd-1; k>=0; --k, ++i)
		dig[i]= n[k]-'0';	
	normal();
}

Numero::Numero(int t)
{
	nd= t;
	dig= new char[t];
	for (int i=0; i<t; ++i)
		dig[i]= 0;	
}

Numero::Numero(const Numero& a)
{
	nd= a.ndig();
	dig= new char[nd];
	for (int k=0; k<nd; ++k)
		dig[k]= a[k];
}

void Numero::div10(void)
{
	--nd;
	for (int k=0; k<nd; ++k)
		dig[k]= dig[k+1];
}

Numero& Numero::operator = (const Numero& n)
{
	delete [] dig;
	nd= n.ndig();
	dig= new char [nd];	
	for (int k=0; k<nd; ++k)
		dig[k]= n[k];
	return *this;
}

Numero::~Numero(void)
{
	delete [] dig;
	nd= 0;
}

void Numero::normal(void)
{
	int k= nd-1;
	while (k>0 && dig[k]==0)
		--k;
	nd= k+1;
}

char  Numero::operator [] (int k) const 
{ 
	return k<nd ? dig[k] : 0; 
};

std::ostream& operator << (std::ostream& out, const Numero& n)
{
	for (int k=n.ndig()-1; k>=0; --k)
		out << char(n[k]+'0');
	return out;
}

std::istream& operator >> (std::istream& inp, Numero& n)
{
	inp >> std::ws;
	std::string s;
	while (isdigit(std::cin.peek())) {
		char t= std::cin.get();;
		s+= t;
	}
	n= Numero(s.c_str());
	return inp;
}

Numero operator + (const Numero& a, const Numero& b)
{
	int nda= a.ndig();
	int ndb= b.ndig();
	int nr= nda >= ndb ? nda : ndb;
	Numero r(nr+1);

	int acarreo=0;
	for (int k=0; k<nr; ++k) {
		int t= a[k] + b[k] + acarreo;
		if (t>=10) {
			acarreo= 1;
			t-= 10;
		}
		else
			acarreo= 0;
		r[k]= t;
	}
	r[nr]= acarreo;
	r.normal();
	return r;
}


Numero operator * (const Numero& a, const Numero& b)
{
	Numero r;
	int nda= a.ndig();
	int ndb= b.ndig();
	for (int i=0; i<ndb; ++i) {
		Numero p(a.ndig()+1+i);
		int m= b[i];
		int c= 0;
		for (int j=0; j<nda; ++j) {
			int t= a[j]*m + c;	
			p[j+i]= t%10;
			c= t/10;
		}
		p[nda+i]= c;
		r= r + p;	
	}
	return r;
}

Numero operator - (const Numero& a, const Numero& b)
{
	int nda= a.ndig();
	int ndb= b.ndig();
	int nr= nda >= ndb ? nda : ndb;
	Numero r(nr);
	int c=0;
	for (int k=0; k<nr; ++k) {
		int t;
		if (a[k] < b[k]+c) {
			t= 10+a[k] - (b[k]+c);
			c= 1;
		}
		else {
			t= a[k] - (b[k]+c);
			c=0;
		}
		r[k]= t;
	}
	r.normal();
	if (c)
		return Numero("0");
	else
		return r;	
}

bool operator < (const Numero& a, const Numero& b)
{
	int nda= a.ndig();
	int ndb= b.ndig();
	int nr= nda >= ndb ? nda : ndb;
	int c=0;
	for (int k=0; k<nr; ++k) {
		int t= a[k] - (b[k]+c);
		if (t<0) {
			t+= 10;
			c= 1;
		}
		else
			c=0;
	}	
	return c!=0;
}

bool operator == (const Numero& a, const Numero& b)
{
	int nda= a.ndig();
	int ndb= b.ndig();
	int nr= nda >= ndb ? nda : ndb;
	for (int k=0; k<nr; ++k) {
		if (a[k] != b[k])
			return false;
	}
	return true;
}

bool operator <= (const Numero& a, const Numero& b)
{
    return a<b || a==b;
}

bool operator != (const Numero& a, const Numero& b)
{
    return  !(a==b);
}

bool operator >= (const Numero& a, const Numero& b)
{
    return !(a<b);
}

bool operator > (const Numero& a, const Numero& b)
{
    return !(a<b || a==b);
}

static
void divmod (const Numero& a, const Numero& b, Numero& q, Numero& r)
{
	Numero d("10");
	Numero u("1");

	if (b=="0") {
		q= "0";
		r= "0";
		return;
	}


	Numero o, t= b;
	do {
		o= t;
		t= d * t;
	} while (t<=a);

	q= Numero("0");
	r= a;
	while (b<=o) {
		q= q * d;
		while (o <= r) {
			r= r-o;
			q= q + u;
		}
		o.div10();
	}
}

Numero operator / (const Numero& a, const Numero& b)
{
	Numero q, r;
	divmod(a, b, q, r);
	return q;
}

Numero operator % (const Numero& a, const Numero& b)
{
	Numero q, r;
	divmod(a, b, q, r);
	return r;
}