bignum

#include <iostream>
#include <iomanip>
#include <vector>

typedef long long lld;

struct Number;

std::ostream& operator<<(std::ostream& os, const Number& num);
int compare (const Number& a, const Number& b);
bool operator<(const Number& a, const Number& b);
bool operator>(const Number& a, const Number& b);
bool operator==(const Number& a, const Number& b);
bool operator!=(const Number& a, const Number& b);
bool operator<=(const Number& a, const Number& b);
bool operator>=(const Number& a, const Number& b);

struct Number {
	static const int POW10 = (int)1e9;
	static const int WIDTH = 9;

	std::vector<int> digits;

	Number(int num = 0) : digits(1, num) { }

	Number(const std::vector<int>& digits) : digits(digits) { }

	Number& operator+=(const Number& other) {
		int s1 = (int)this->digits.size();
		int s2 = (int)other.digits.size();
		int carry = 0;
		for (int i = 0; i < s1 || i < s2 || carry > 0; ++i) {
			int d1 = i < s1 ? this->digits[i] : 0;
			int d2 = i < s2 ? other.digits[i] : 0;
			carry += d1 + d2;
			int digit = carry % POW10;
			carry /= POW10;
			if (i < s1) {
				this->digits[i] = digit;
			} else {
				this->digits.push_back(digit);
			}
		}
		return *this;
	}

	Number& operator-=(const Number& other) {
		int s1 = (int)this->digits.size();
		int s2 = (int)other.digits.size();
		int rem = 0;
		for (int i = 0; i < s1 || i < s2 || rem; ++i) {
			this->digits[i] -= (i < s2 ? other.digits[i] : 0) + rem;
			rem = 0;
			if (this->digits[i] < 0) {
				this->digits[i] += POW10;
				++rem;
			}
		}

		while ((int)digits.size() > 1 && digits.back() == 0) {
			digits.pop_back();
		}

		return *this;
	}


	Number& operator*=(const int num) {
		int s = (int)digits.size();
		lld carry = 0;
		for (int i = 0; i < s || carry; ++i) {
			carry += 1LL * num * (i < s ? this->digits[i] : 0);
			int digit = carry % POW10;
			carry /= POW10;
			if (i < s) {
				this->digits[i] = digit;
			} else {
				this->digits.push_back(digit);
			}
		}

		while ((int)digits.size() > 1 && digits.back() == 0) {
			digits.pop_back();
		}

		return *this;
	}

	Number operator*(const Number& other) const {
		int s1 = (int)this->digits.size();
		int s2 = (int)other.digits.size();
		std::vector<int> answer(s1+s2);
		for (int i = 0; i < s1; ++i) {
			lld carry = 0;
			for (int j = 0; j < s2; ++j) {
				carry += answer[i+j] + 1LL * this->digits[i] * other.digits[j];
				answer[i+j] = carry % POW10;
				carry /= POW10;
			}
			if (carry > 0) {
				answer[i+s2] += carry;
			}
		}
		while ((int)answer.size() > 1 && answer.back() == 0) {
			answer.pop_back();
		}

		return Number(answer);
	}

	Number operator/ (const Number& other) {
		Number answer = 0, curr = 0;
		for (int i = (int)this->digits.size()-1; i >= 0; --i) {
			std::cout << "\nbefore shift: " << curr << std::endl;
			curr.shift(1); // * POW10
			std::cout << "after shift: " << curr << std::endl << std::endl;
			curr.digits[0] = this->digits[i];
			// подбираем максимальное число x, такое что b * x <= curValue
			int x = 0, l = 0, r = POW10;
			while (l <= r) {
				int m = (l + r) >> 1;
				Number temp = other * m;
				if (temp <= curr) {
					x = m;
					l = m+1;
				} else {
					r = m-1;
				}
			}
			answer.digits[i] = x;
			curr -= other * x;
		}
		// избавляемся от лидирующих нулей
		while ((int)answer.digits.size() > 1 && answer.digits.back() == 0) {
			answer.digits.pop_back();
		}

		return answer;
	}

	Number& shift(int value) {
		if (value > 0) {
			for (int i = 0; i < value; ++i) {
				digits.push_back(0);
			}
			for (int i = (int)digits.size()-1; i >= value; --i) {
				digits[i] = digits[i-value];
			}
			for (int i = value-1; i >= 0; --i) {
				digits[i] = 0;
			}
		} else if (value < 0) {
			value = -value;
			if (value >= (int)digits.size()) {
				digits.assign(1, 0);
				return *this;
			}
			for (int i = 0; i <= (int)digits.size()-1-value; ++i) {
				digits[i] = digits[i+value];
			}
			for (int i = 0; i < value; ++i) {
				digits.pop_back();
			}
		}

		while ((int)digits.size() > 1 && digits.back() == 0) {
			digits.pop_back();
		}

		return *this;
	}
};

std::ostream& operator<<(std::ostream& os, const Number& num) {
	os << num.digits.back();
	for (int i = (int)num.digits.size()-2; i >= 0; --i) {
		os << std::setw(Number::WIDTH) << std::setfill('0') << num.digits[i];
	}
	return os << std::setfill(' ');
}

int compare (const Number& a, const Number& b) {
	if (a.digits.size() < b.digits.size()) {
		return -1;
	}

	if (a.digits.size() > b.digits.size()) {
		return 1;
	}

	for (int i = (int)a.digits.size()-1; i >= 0; --i) {
		if (a.digits[i] < b.digits[i]) {
			return -1;
		} else if (a.digits[i] > b.digits[i]) {
			return 1;
		}
	}
	return 0;
}

bool operator<(const Number& a, const Number& b) {
	return compare(a, b) == -1;
}

bool operator>(const Number& a, const Number& b) {
	return compare(a, b) == 1;
}

bool operator==(const Number& a, const Number& b) {
	return compare(a, b) == 0;
}

bool operator!=(const Number& a, const Number& b) {
	return compare(a, b) != 0;
}

bool operator<=(const Number& a, const Number& b) {
	return compare(a, b) <= 0;
}

bool operator>=(const Number& a, const Number& b) {
	return compare(a, b) >= 0;
}

int main() {
	Number a = 1, b = 1, c = 1;
	for (int i = 1; i <= 100; ++i) {
		a *= 2;
		b *= 3;
		c *= 6;
	}

	std::cout << "compare:"<< std::endl;
	std::cout << "\t" <<a*b << std::endl;
	std::cout << "\t" << c << std::endl;

	std::cout << "compare:"<< std::endl;
	std::cout << "\t" << c / a << std::endl;
	std::cout << "\t" << b << std::endl;

	std::cout << "compare:"<< std::endl;
	std::cout << "\t" << c / b << std::endl;
	std::cout << "\t" << a << std::endl;

	return 0;
}