using std::istream;
using std::ostream;
using std::getchar;
namespace math{
template<typename T>
T gcd(T x,T y){
if(x<y){
int temp=x;
x=y,y=temp;
}
int z;
while(y!=0){
z=x%y,x=y,y=z;
}
return x;
}
template<typename T>
T lcm(T x,T y){
return x/gcd(x,y)*y;
}
}
template<typename T,typename Tvalue=double> //T==int,long long,your big_int class ......
class fraction{
private:
T _up,_down;
bool input_with_reduction,output_with_reduction,multi_optimize;
//optimize指上界优化，即：以牺牲时间为代价换取不溢出
public:
// constructors
fraction(){
_up=1,_down=1,input_with_reduction=output_with_reduction=1,multi_optimize=0;
}
fraction(T up,T down){
_up=up,_down=down,input_with_reduction=output_with_reduction=1,multi_optimize=0;
if(input_with_reduction) reduction();
}
fraction(bool optimize){
_up=1,_down=1,input_with_reduction=output_with_reduction=1,multi_optimize=optimize;
}
fraction(T up,T down,bool optimize){
_up=up,_down=down,input_with_reduction=output_with_reduction=1,multi_optimize=optimize;
if(input_with_reduction) reduction();
}
fraction(bool input_reduct,bool output_reduct){
_up=1,_down=1,input_with_reduction=input_reduct,output_with_reduction=output_reduct,
multi_optimize=0;
}
fraction(T up,T down,bool input_reduct,bool output_reduct){
_up=up,_down=down,input_with_reduction=input_reduct,output_with_reduction=output_reduct,
multi_optimize=0;
if(input_with_reduction) reduction();
}
fraction(bool input_reduct,bool output_reduct,bool optimize){
_up=1,_down=1,input_with_reduction=input_reduct,output_with_reduction=output_reduct,
multi_optimize=optimize;
}
fraction(T up,T down,bool input_reduct,bool output_reduct,bool optimize){
_up=up,_down=down,input_with_reduction=input_reduct,output_with_reduction=output_reduct,
multi_optimize=optimize;
if(input_with_reduction) reduction();
}
// inputs
friend istream& operator >> (istream& input,fraction<T>& the_frac){
if(the_frac.input_with_reduction) the_frac.reduction();
input>>the_frac._up;
getchar();
input>>the_frac._down;
return input;
}
fraction<T> input_cin(bool with_reduction=1){
if(with_reduction) reduction();
using std::cin;
cin>>_up;
getchar();
cin>>_down;
return *this;
}
// outputs
friend ostream& operator << (ostream& output,fraction<T> the_frac){
if(the_frac.output_with_reduction) the_frac.reduction();
output<<the_frac._up<<'/'<<the_frac._down;
return output;
}
fraction<T> output_cout(bool with_reduction=1){
if(with_reduction) reduction();
using std::cout;
cout<<_up<<'/'<<_down;
return *this;
}
// basic_functions
T up(){
return _up;
}
T down(){
return _down;
}
// (bool change)
bool input_reduction(bool change_to){
input_with_reduction=change_to;
return change_to;
}
bool output_reduction(bool change_to){
output_with_reduction=change_to;
return change_to;
}
bool multi_optimize_change(bool change_to){
multi_optimize=change_to;
return change_to;
}
bool all_reduction(bool input_change_to,bool output_change_to){
input_with_reduction=input_change_to,output_with_reduction=output_change_to;
return input_change_to&&output_change_to;
}
bool all_bool_change(bool input_change_to,bool output_change_to,bool optimize_change_to){
input_with_reduction=input_change_to,output_with_reduction=output_change_to,
multi_optimize=optimize_change_to;
return (input_change_to&&output_change_to)^optimize_change_to;
}
// (end of bool change)
template<typename Tans=Tvalue>
Tans value()const{
return Tans(_up)/Tans(_down);
}
fraction<T> reduction(){ //约分
T gcd_result=math::gcd(_up,_down);
_up/=gcd_result,_down/=gcd_result;
return *this;
}
fraction<T> reciprocal(bool with_reduction=1)const{
return fraction<T>(_down,_up,with_reduction,1);
}
template<typename T1,typename T2=T1>
static void common(fraction<T1> &frac_x,fraction<T2> &frac_y){ //通分
T gcd_num=math::gcd(frac_x._down,frac_y._down);
T1 x_multi_num=frac_y._down/gcd_num,y_multi_num=frac_x._down/gcd_num;
frac_x._down*=x_multi_num,frac_x._up*=x_multi_num;
frac_y._down*=y_multi_num,frac_y._up*=y_multi_num;
}
operator Tvalue()const{
return Tvalue(_up)/Tvalue(_down);
}
// operator + , - , * , /
// operator +
fraction<T> operator + (T another_adder)const{
fraction<T> frac_adder(another_adder*_down,_down,0,0);
return fraction<T>(_up+frac_adder._up,_down,1,1);
}
fraction<T> operator + (fraction<T> another_adder)const{
two_fracs<T> commoned=common_value(*this,another_adder);
return fraction<T>(._up+._up,._down,true,true);
}
friend fraction<T> operator + (T adder,fraction<T> frac_adder){
fraction<T> frac_adder_eq1(adder*frac_adder._down,frac_adder._down,false,false);
return fraction<T>(frac_adder._up+frac_adder_eq1._up,frac_adder._down,true,true);
}
//operator -
fraction<T> operator - (fraction<T> another_adder)const{
two_fracs<T> commoned=common_value(*this,another_adder);
return fraction<T>(._up._up,._down,true,true);
}
friend fraction<T> operator - (T adder,fraction<T> frac_adder){
fraction<T> frac_adder_eq1(adder*frac_adder._down,frac_adder._down,false,false);
return fraction<T>(frac_adder_eq1._up-frac_adder._up,frac_adder._down,true,true);
}
//operator *
fraction<T> operator * (T another_adder){
T gcd_num;
if((gcd_num=math::gcd(_down,another_adder))!=1)
_down/=gcd_num,another_adder/=gcd_num;
return fraction<T>(_up*another_adder,_down,false,false);
}
fraction<T> operator * (fraction<T> another_adder){
if(multi_optimize){
T gcd_num;
if(math::gcd(_up,_down)!=1) reduction();
if(math::gcd(another_adder._up,another_adder._down)!=1) another_adder.reduction();
if((gcd_num=math::gcd(_up,another_adder._down))!=1)
_up/=gcd_num,another_adder._down/=gcd_num;
if((gcd_num=math::gcd(_down,another_adder._up)!=1))
_down/=gcd_num,another_adder._up/=gcd_num;
return fraction<T>(_up*another_adder._up,_down*another_adder._down,false,false);
}
else{
return fraction<T>(_up*another_adder._up,_down*another_adder._down,true,true);
}
}
friend fraction<T> operator * (T adder,fraction<T> frac_adder){
T gcd_num;
if((gcd_num=math::gcd(frac_adder._down,adder))!=1)
frac_adder._down/=gcd_num,adder/=gcd_num;
return fraction<T>(frac_adder._up*adder,frac_adder._down,false,false);
}
//operator /
fraction<T> operator / (T divider){
return operator * (fraction<T>(divider,1,multi_optimize));
}
fraction<T> operator / (fraction<T> divider){
return operator * (divider.reciprocal(!multi_optimize));
}
friend fraction<T> operator / (T dividend,fraction<T> divider){
return operator * (dividend,divider.reciprocal(false));
}
// operator < , == , != , > , <= , >=
// operator <
bool operator < (fraction<T> frac_arg)const{
two_fracs<T> commoned=common_value(*this,frac_arg);
return ._up<._up;
}
bool operator < (T integer_arg)const{
fraction<T> frac_arg_eqint(integer_arg*_down,_down,false,false);
return _up<frac_arg_eqint._up;
}
friend bool operator < (T integer_arg,fraction<T> frac_arg){
fraction<T> frac_arg_eqint(integer_arg*frac_arg._down,frac_arg._down,false,false);
return frac_arg._up<frac_arg_eqint._up;
}
// operator ==
bool operator == (fraction<T> frac_arg)const{
two_fracs<T> commoned=common_value(*this,frac_arg);
return ._up==._up;
}
bool operator == (T integer_arg)const{
fraction<T> frac_arg_eqint(integer_arg*_down,_down,false,false);
return _up==frac_arg_eqint._up;
}
friend bool operator == (T integer_arg,fraction<T> frac_arg){
fraction<T> frac_arg_eqint(integer_arg*frac_arg._down,frac_arg._down,false,false);
return frac_arg._up==frac_arg_eqint._up;
}
// operator !=
bool operator != (fraction<T> frac_arg)const{
two_fracs<T> commoned=common_value(*this,frac_arg);
return ._up!=._up;
}
bool operator != (T integer_arg)const{
fraction<T> frac_arg_eqint(integer_arg*_down,_down,false,false);
return _up!=frac_arg_eqint._up;
}
friend bool operator != (T integer_arg,fraction<T> frac_arg){
fraction<T> frac_arg_eqint(integer_arg*frac_arg._down,frac_arg._down,false,false);
return frac_arg._up!=frac_arg_eqint._up;
}
// operator >
bool operator > (fraction<T> frac_arg)const{
two_fracs<T> commoned=common_value(*this,frac_arg);
return ._up>._up;
}
bool operator > (T integer_arg)const{
fraction<T> frac_arg_eqint(integer_arg*_down,_down,false,false);
return _up>frac_arg_eqint._up;
}
friend bool operator > (T integer_arg,fraction<T> frac_arg){
fraction<T> frac_arg_eqint(integer_arg*frac_arg._down,frac_arg._down,false,false);
return frac_arg._up>frac_arg_eqint._up;
}
// operator <=
bool operator <= (fraction<T> frac_arg)const{
two_fracs<T> commoned=common_value(*this,frac_arg);
return ._up<=._up;
}
bool operator <= (T integer_arg)const{
fraction<T> frac_arg_eqint(integer_arg*_down,_down,false,false);
return _up<=frac_arg_eqint._up;
}
friend bool operator <= (T integer_arg,fraction<T> frac_arg){
fraction<T> frac_arg_eqint(integer_arg*frac_arg._down,frac_arg._down,false,false);
return frac_arg._up<=frac_arg_eqint._up;
}
// operator >=
bool operator >= (fraction<T> frac_arg)const{
two_fracs<T> commoned=common_value(*this,frac_arg);
return ._up>=._up;
}
bool operator >= (T integer_arg)const{
fraction<T> frac_arg_eqint(integer_arg*_down,_down,false,false);
return _up>=frac_arg_eqint._up;
}
friend bool operator >= (T integer_arg,fraction<T> frac_arg){
fraction<T> frac_arg_eqint(integer_arg*frac_arg._down,frac_arg._down,false,false);
return frac_arg._up>=frac_arg_eqint._up;
}
// operator += , -= , *= , /=
// operator +=
fraction<T> operator += (fraction<T> add_num){
return *this=*this+add_num;
}
fraction<T> operator += (T add_num){
return *this=*this+add_num;
}
friend fraction<T> operator += (T add_num,fraction<T> add_frac){
return add_frac=add_frac+add_num;
}
// operator -=
fraction<T> operator -= (fraction<T> add_num){
return *this=*this-add_num;
}
fraction<T> operator -= (T add_num){
return *this=*this-add_num;
}
friend fraction<T> operator -= (T add_num,fraction<T> add_frac){
return add_frac=add_frac-add_num;
}
// operator *=
fraction<T> operator *= (fraction<T> add_num){
return *this=*this*add_num;
}
fraction<T> operator *= (T add_num){
return *this=*this*add_num;
}
friend fraction<T> operator *= (T add_num,fraction<T> add_frac){
return add_frac=add_frac*add_num;
}
// operator /=
fraction<T> operator /= (fraction<T> add_num){
return *this=*this/add_num;
}
fraction<T> operator /= (T add_num){
return *this=*this/add_num;
}
friend fraction<T> operator /= (T add_num,fraction<T> add_frac){
return add_frac=add_frac/add_num;
}
private:
template<typename T1,typename T2=T1>
struct two_fracs{
fraction<T1> first;
fraction<T2> second;
two_fracs(){}
two_fracs(fraction<T1> new_1,fraction<T2> new_2){
first=new_1,second=new_2;
}
};
template<typename T1,typename T2=T1>
static two_fracs<T1,T2> common_value(fraction<T1> frac_x,fraction<T2> frac_y){
T1 gcd_num=math::gcd(frac_x._down,frac_y._down);
T1 x_multi_num=frac_y._down/gcd_num,y_multi_num=frac_x._down/gcd_num;
frac_x._down*=x_multi_num,frac_x._up*=x_multi_num;
frac_y._down*=y_multi_num,frac_y._up*=y_multi_num;
return two_fracs<T1,T2>(frac_x,frac_y);
}
};
namespace math{
template<typename T>
fraction<T> reduction(fraction<T> the_frac){
return the_frac.reduction();
}
}