fraction.cpp

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a,b) * b; }

template<class T>
class Fraction{
	void normalize(){
		if(p == 0){
			q = 1;
		} else {
			T g = gcd(p,q);
			p = p / g;
			q = q / g;
			if(q < 0){
				p *= -1;
				q *= -1;
			}
		}
	}
public:
	T p,q; // p/q

	Fraction() : p(0) , q(1) {}
	Fraction(T n) : p(n) , q(1) {}
	Fraction(T p,T q) : p(p) , q(q) {
		normalize();
	}

	Fraction operator+(const Fraction& l) const {
		T np = this->p * l.q + this->q * l.p;
		T nq = this->q * l.q;
		return Fraction(np,nq);
	}

	Fraction operator-(const Fraction& l) const {
		T np = this->p * l.q - this->q * l.p;
		T nq = this->q * l.q;
		return Fraction(np,nq);
	}

	Fraction operator*(const Fraction& l) const {
		T np = this->p * l.p;
		T nq = this->q * l.q;
		return Fraction(np,nq);
	}

	Fraction operator/(const Fraction& l) const {
		T np = this->p * l.q;
		T nq = this->q * l.p;
		return Fraction(np,nq);
	}

	Fraction operator+=(const Fraction& l){
		Fraction tmp = *this + l;
		this->p = tmp.p;
		this->q = tmp.q;
	}

	Fraction operator-=(const Fraction& l){
		Fraction tmp = *this - l;
		this->p = tmp.p;
		this->q = tmp.q;
	}

	Fraction operator*=(const Fraction& l){
		Fraction tmp = *this * l;
		this->p = tmp.p;
		this->q = tmp.q;
	}

	Fraction operator/=(const Fraction& l){
		Fraction tmp = *this / l;
		this->p = tmp.p;
		this->q = tmp.q;
	}

	bool operator<(const Fraction& l) const{ return p * l.q < q * l.p; }
	bool operator<=(const Fraction& l) const{ return p * l.q <= q * l.p; }
	bool operator>(const Fraction& l) const{ return p * l.q > q * l.p; }
	bool operator>=(const Fraction& l) const{ return p * l.q >= q * l.p; }
	bool operator==(const Fraction& l) const{ return p * l.q == q * l.p; }
};

template<class T>
std::ostream& operator<<(std::ostream& os,const Fraction<T>& f){
	if(f.q == 0) os << 0;
	else os << f.p << " / " << f.q;
	return os;
}

typedef Fraction<ll> F;