10814 - Simplifying Fractions

[sunnycare]

how to get GCD faster....?

[Cho]

Should I assume you know Euclid's algorithm?
It computes the GCD of two n-bit numbers in O(log n) iterations.

[sunnycare]

i use it..

but got tle...
i think the class BigInteger is correct,for i have solved many problems by it...

the class is too long ,so i wont paste here now....

Code: Select all

BigInteger gcd(BigInteger a,BigInteger b)
{
    BigInteger tmp;
    if(a==0)
    	return b;
   	while(a!=0)
   	{
   	    tmp=b%a;
   	    if(tmp==0)
   	    	return a;
   	    else
        {
            a=a%tmp;
            b=tmp;
        }
    }
    return b;
}

int main()
{
    BigInteger a,b,c;
    long testCase;
    cin>>testCase;
    while(testCase-->=1)
    {
        char ch;
        cin>>a>>ch>>b;
        c=gcd(a,b);
        a=a/c;
        b=b/c;
        cout<<a<<" / "<<b<<endl;
    }
}

[mf]

Most likely it's because your BigInteger's division is too slow. Better try to optimize that code first.

As for gcd, there's a so-called "binary gcd" algorithm, which uses only shifts and subtractions. Here's a pseudo-code for it:

Code: Select all

gcd(a, b):   /* assumes a >= 0, b >= 0, a*b > 0 */
	g = 0
	while both a and b are even:
		g++, a /= 2, b /= 2;

	while a != 0 and b != 0:
		while a is even: a /= 2
		while b is even: b /= 2

		if a > b:
			a -= b
		else:
			b -= a

	if a == 0:
		return b << g
	else:
		return a << g

[sunnycare]

Most likely it's because your BigInteger's division is too slow. Better try to optimize that code first

i have generate a lot of input data to test my code
it works so fast...

how to optimize the BigInteger's division ?can you give me some advise?

[/code]

[mf]

Check how fast you can pass this input:

Code: Select all

5
36893487443044468898 / 36893487958440542378
999999999999872000000000001287 / 999999999999936000000000000583
999999999999999999999999999999 / 6
30 / 1000000000000000000000000000000
304888344611713860501504000000 / 40729680599249024150621323470

The output should be:

Code: Select all

4294967231 / 4294967291
999999999999883 / 999999999999947
333333333333333333333333333333 / 2
3 / 100000000000000000000000000000
1366643159020339200000 / 182568275710689562381

For division you can use just the usual long division, taught at school. It's quite efficient for this problem.

[Abednego]

How do the copy constructor and assignment operator in your BigInteger work? If they create new arrays all the time, that will take a lot of time. Try to avoid allocating new memory as much as possible.

[sunnycare]

hi mf my code works ok and fast for your sample input..
so i think i should paste my whole code here......

any suggesstion is welcome...thanks

Code: Select all

//10814 Simplifying Fractions
#include <iostream>
#include <cmath>
#include <string>
using namespace std;



class BigInteger
{

private:
	enum {MAXNUM=999999999,BASE=1000000000,MAXLENGTH=32};
    long val[MAXLENGTH];
	long length;
public:	
	//////////////////////////////////
	BigInteger(long n=0);
	BigInteger(const string &str);
	BigInteger(long *pVal,long len);
	//////////////////////////////////
	BigInteger(const BigInteger &p);
	/////////////////////////////////
	BigInteger & operator =(const BigInteger &rval);
	BigInteger & operator =(long rval);
	BigInteger & operator =(const string &str);
	//////////////////////////////////
	virtual ~BigInteger(){}
	///////////////////////////////////
	long Compare(const BigInteger &rval);
	long Compare(long rval);
	long Compare(const string &rval);
    BigInteger Sqrt();
	
	BigInteger operator +(const BigInteger &rval);
	BigInteger operator +(long rval);
	BigInteger operator +(const string &rval);
	BigInteger &operator +=(const BigInteger &rval);
	BigInteger &operator +=(long rval);
	BigInteger &operator +=(const string &rval);
	

	BigInteger operator -(const BigInteger &rval);
	BigInteger operator -(long rval);
	BigInteger operator -(const string &rval);
	BigInteger &operator -=(const BigInteger &rval);
	BigInteger &operator -=(long rval);
	BigInteger &operator -=(const string &rval);

	BigInteger operator *(const BigInteger &rval);
	BigInteger operator *(long rval);
	BigInteger operator *(const string &rval);
	BigInteger &operator *=(const BigInteger &rval);
	BigInteger &operator *=(long rval);
	BigInteger &operator *=(const string &rval);
	
	BigInteger operator /(const BigInteger &rval);
	BigInteger operator /(long rval);
	BigInteger operator /(const string &rval);
	BigInteger &operator /=(const BigInteger &rval);
	BigInteger &operator /=(long rval);
	BigInteger &operator /=(const string &rval);

	BigInteger operator %(const BigInteger &rval);
	BigInteger operator %(long rval);
	BigInteger operator %(const string &rval);
	BigInteger &operator %=(const BigInteger &rval);
	BigInteger &operator %=(long rval);
	BigInteger &operator %=(const string &rval);

	
	BigInteger &operator ++();
	BigInteger operator ++(int);
	BigInteger &operator --(); 
	BigInteger operator --(int);
	
		
	bool operator >(const BigInteger &rval);
	bool operator >(long rval);
	bool operator >(const string &rval);

	bool operator <(const BigInteger &rval);
	bool operator <(long rval);
	bool operator <(const string &rval);

	bool operator >=(const BigInteger &rval);
	bool operator >=(long rval);
	bool operator >=(const string &rval);

	bool operator <=(const BigInteger &rval);
	bool operator <=(long rval);
	bool operator <=(const string &rval);

	bool operator ==(const BigInteger &rval);
	bool operator ==(long rval);
	bool operator ==(const string &rval);

	bool operator !=(const BigInteger &rval);
	bool operator !=(long rval);
	bool operator !=(const string &rval);
	
	friend ostream & operator<<(ostream &out,const BigInteger &p);
	friend istream & operator>>(istream &in,BigInteger &p);

	
};

BigInteger::BigInteger(long n)
{
    val[0]=n;
    length=1;
}
BigInteger::BigInteger(const string &str)
{
    long tab[10]={1,10,100,1000,10000,100000,1000000,
		10000000,100000000,1000000000};
	long i,j,k,l;
	long tmp;
    l=str.length();
	length=(l-1)/9+1;
	for(i=0;i<length;i++)
	{
		tmp=0;
		for(j=l-i*9-1,k=0;j>l-1-(i+1)*9&&j>=0;j--,k++)
		{

			tmp+=tab[k]*(str[j]-'0');
		}
		val[i]=tmp;
	}
}
BigInteger::BigInteger(long *pVal,long len)
{
    long i;
    length=len;
    for(i=0;i<len;i++)
        val[i]=pVal[i];
}

BigInteger::BigInteger(const BigInteger &p)
{
    length=p.length;
    long i=0;
    while(i<length)
    {
        val[i]=p.val[i];
        ++i;
    }
}
BigInteger & BigInteger:: operator =(const BigInteger &rval)
{
    length=rval.length;
    long i=0;
    for(;i<length;++i)
        val[i]=rval.val[i];
}
BigInteger & BigInteger::operator =(long rval)
{
    length=1;
    val[0]=rval;
}
BigInteger & BigInteger::operator =(const string &str)
{
    long tab[10]={1,10,100,1000,10000,100000,1000000,
		10000000,100000000,1000000000};
	long i,j,k,l;
	long tmp;
    l=str.length();
	length=(l-1)/9+1;
	for(i=0;i<length;i++)
	{
		tmp=0;
		for(j=l-i*9-1,k=0;j>l-1-(i+1)*9&&j>=0;j--,k++)
		{

			tmp+=tab[k]*(str[j]-'0');
		}
		val[i]=tmp;
	}
}
long BigInteger::Compare(const BigInteger &rval)
{
    //this==rval return 0;
	//this>rval return 1;
	//this<rval return -1;
	long i;
	if(length>rval.length)
		return 1;
	else
	{
		if(length<rval.length)
			return -1;
		else
		{
			for(i=length-1;i>=0;i--)
			{
				if(val[i]>rval.val[i])
					return 1;
				else
					if(val[i]<rval.val[i])
						return -1;
			}
			return 0;
		}
	}

}
long BigInteger::Compare(long rval)
{
    BigInteger tmp(rval);
    return Compare(tmp);
}
long BigInteger::Compare(const string &rval)
{
    BigInteger tmp(rval);
    return Compare(tmp);
}
BigInteger BigInteger::Sqrt()
{
    BigInteger x;
    if(length==1)
    {
        x.length=1;
        x.val[0]=(long)sqrt((double)val[0]);
    }
    else
    {
        BigInteger m,dx,t;
        long cmp;
	    x.length=(length-1)/2+1;
	    x.val[x.length-1]=(long)sqrt((double)val[length-1]);
	    if(length%2==0)
      		x.val[x.length-1]*=31622;
   		while(1)
   		{
        	m=operator/(x);
        	cmp=m.Compare(x);
        	if(cmp==0)
       			break;
  			else
        	{
        		if(cmp==1)
         		{
                    dx=(m-x)/2;
             		x+=dx;
           		}
           		else
           		{
            		dx=(x-m)/2;
              		x-=dx;
           		}
       		}
   		}
   	}
    return x;
}
BigInteger BigInteger::operator +(const BigInteger &rval)
{
    BigInteger sum;
    long tmp;
	long n=0;
	if(length>rval.length)
		tmp=rval.length;
	else
		tmp=length;
	long i;
	long carry=0;
	for(i=0;i<tmp;++i)
	{
		sum.val[i]=val[i]+rval.val[i]+carry;
		if(sum.val[i]>MAXNUM)
		{
			sum.val[i]-=MAXNUM+1;
			carry=1;
		}
		else
			carry=0;
	}
	n=tmp;
	for(;i<length;++i)
	{
		sum.val[i]=val[i]+carry;
		if(sum.val[i]>MAXNUM)
		{
			sum.val[i]-=MAXNUM+1;
			carry=1;
		}
		else
		{
			carry=0;
		}
		++n;
	}
	for(;i<rval.length;++i)
	{
		sum.val[i]=rval.val[i]+carry;
		if(sum.val[i]>MAXNUM)
		{
			sum.val[i]-=MAXNUM+1;
			carry=1;
		}
		else
		{
			carry=0;
		}
		n++;
	}
	if(carry==1)
	{
		sum.val[i]=1;
		n++;
	}
	sum.length=n;
    return sum;

}
BigInteger BigInteger::operator +(long rval)
{
    BigInteger tmp(rval);
    return operator+(tmp);
}
BigInteger BigInteger::operator +(const string &rval)
{
    BigInteger tmp(rval);
    return operator+(tmp);
}
BigInteger & BigInteger::operator +=(const BigInteger &rval)
{
    BigInteger sum=this->operator+(rval);
    this->operator=(sum);
    return *this;
}
BigInteger & BigInteger::operator +=(long rval)
{
    BigInteger tmp(rval);
    BigInteger sum=this->operator+(tmp);
    this->operator=(sum);
    return *this;
}
BigInteger & BigInteger::operator +=(const string &rval)
{
    BigInteger tmp(rval);
    BigInteger sum=this->operator+(tmp);
    this->operator=(sum);
    return *this;
}
BigInteger BigInteger::operator -(const BigInteger &rval)
{
    BigInteger sub;
    long tmp;
	long n=0;
	if(Compare(rval)==0)
	   return BigInteger(0);
	if(Compare(rval)==1)
		tmp=rval.length;
	else
		tmp=length;
	long i;
	long carry=0;
	for(i=0;i<tmp;++i)
	{
		sub.val[i]=val[i]-rval.val[i]-carry;
		if(sub.val[i]<0)
		{
			sub.val[i]+=BASE;
			carry=1;
		}
		else
			carry=0;
	}
	n=tmp;
	for(;i<length;++i)
	{
		sub.val[i]=val[i]-carry;
		if(sub.val[i]<0)
		{
			sub.val[i]+=BASE;
			carry=1;
		}
		else
		{
			carry=0;
		}
		n++;
	}
	for(;i<rval.length;++i)
	{
		sub.val[i]=rval.val[i]-carry;
		if(sub.val[i]<0)
		{
			sub.val[i]+=BASE;
			carry=1;
		}
		else
		{
			carry=0;
		}
		n++;
	}
	if(sub.val[n-1]==0)
		n--;
	sub.length=n;
    return sub;
}
BigInteger BigInteger::operator -(long rval)
{
    BigInteger tmp(rval);
    return operator-(tmp);
}
BigInteger BigInteger::operator -(const string &rval)
{
    BigInteger tmp(rval);
    return operator-(tmp);
}
BigInteger & BigInteger::operator -=(const BigInteger &rval)
{
    BigInteger sub=this->operator-(rval);
    this->operator=(sub);
    return *this;
}
BigInteger & BigInteger::operator -=(long rval)
{
    BigInteger tmp(rval);
    BigInteger sub=this->operator-(rval);
    this->operator=(sub);
    return *this;
}
BigInteger & BigInteger::operator -=(const string &rval)
{
    BigInteger tmp(rval);
    BigInteger sub=this->operator-(rval);
    this->operator=(sub);
    return *this;
}
BigInteger BigInteger::operator *(const BigInteger &rval)
{
    BigInteger mul;
    long an=length;
	long bn=rval.length;
	long i,j;
	long mul_carry,add_carry;
	long long tmp;
	for(i=0;i<MAXLENGTH;++i)
		mul.val[i]=0;
	for(i=0;i<an;++i)
	{
		mul_carry=0;
		add_carry=0;
		for(j=0;j<bn;++j)
		{
			tmp=(long long)(val[i])*(long long)(rval.val[j])+mul_carry;
			mul.val[i+j]+=tmp%BASE+add_carry;
			if(mul.val[i+j]>=BASE)
			{
				mul.val[i+j]-=BASE;
				add_carry=1;
			}
			else
			{
				add_carry=0;
			}
			mul_carry=tmp/BASE;
		}
		mul.val[i+j]+=mul_carry+add_carry;
	}
	for(i=MAXLENGTH-1;i>=0;--i)
		if(mul.val[i]!=0)
			break;
	if(i>=0)
		mul.length=i+1;
	else
		mul.length=1;
    return mul;
}
BigInteger BigInteger::operator *(long rval)
{
    BigInteger tmp(rval);
    return operator*(tmp);
}
BigInteger BigInteger::operator *(const string &rval)
{
    BigInteger tmp(rval);
    return operator*(tmp);
}
BigInteger & BigInteger::operator *=(const BigInteger &rval)
{
    BigInteger mul=this->operator*(rval);
    this->operator=(mul);
    return *this;
}
BigInteger & BigInteger::operator *=(long rval)
{
    BigInteger mul=this->operator*(rval);
    this->operator=(mul);
    return *this;
}
BigInteger & BigInteger::operator *=(const string &rval)
{
    BigInteger mul=this->operator*(rval);
    this->operator=(mul);
    return *this;
}
	
BigInteger BigInteger::operator /(const BigInteger &rval)
{
    BigInteger div,mod;
    long tmp=Compare(rval);
    if(tmp==1)
    {
        long i,j,k;
        div.length=length-rval.length+1;
        BigInteger table[32];
        table[0]=rval;
        for(i=1;i<32;++i)
        	table[i]=table[i-1]+table[i-1];

        for(i=length-1,j=rval.length-2;j>=0;--i,--j)
        	mod.val[j]=val[i];
        mod.length=rval.length-1;

        for(i=length-rval.length;i>=0;--i)
        {
          	for(j=mod.length-1;j>=0;--j)
          	{
                mod.val[j+1]=mod.val[j];
            }
            mod.val[0]=val[i];
            if(mod.val[mod.length]!=0)
                ++mod.length;
            for(j=30,div.val[i]=0,k=(1<<30);j>=0;--j,k=(k>>1))
            {
                if(mod.Compare(table[j])>=0)
                {
                    div.val[i]|=k;
                    mod-=table[j];

                }
            }

        }
        while(div.val[div.length-1]==0)
        	--div.length;
    }
    else
    {
        if(tmp==-1)
        {
            div=0;
        }
        else
        {
        	div=1;
       	}
    }
    return div;
}
BigInteger BigInteger::operator /(long rval)
{
    BigInteger tmp(rval);
    return operator/(tmp);
}
BigInteger BigInteger::operator /(const string &rval)
{
    BigInteger tmp(rval);
    return operator/(tmp);
}
BigInteger & BigInteger::operator /=(const BigInteger &rval)
{
    BigInteger div=this->operator/(rval);
    this->operator=(div);
    return *this;
}
BigInteger & BigInteger::operator /=(long rval)
{
    BigInteger div=this->operator/(rval);
    this->operator=(div);
    return *this;
}
BigInteger & BigInteger::operator /=(const string &rval)
{
    BigInteger div=this->operator/(rval);
    this->operator=(div);
    return *this;
}
BigInteger BigInteger::operator %(const BigInteger &rval)
{
    BigInteger div,mod;
    long tmp=Compare(rval);
    if(tmp==1)
    {
        long i,j,k;
        div.length=length-rval.length+1;
        BigInteger table[32];
        table[0]=rval;
        for(i=1;i<32;++i)
        	table[i]=table[i-1]+table[i-1];

        for(i=length-1,j=rval.length-2;j>=0;--i,--j)
        	mod.val[j]=val[i];
        mod.length=rval.length-1;

        for(i=length-rval.length;i>=0;--i)
        {
          	for(j=mod.length-1;j>=0;--j)
          	{
                mod.val[j+1]=mod.val[j];
            }
            mod.val[0]=val[i];
            if(mod.val[mod.length]!=0)
                ++mod.length;
            for(j=30,div.val[i]=0,k=(1<<30);j>=0;--j,k=(k>>1))
            {
                if(mod.Compare(table[j])>=0)
                {
                    div.val[i]|=k;
                    mod-=table[j];

                }
            }

        }
        
    }
    else
    {
        if(tmp==-1)
        {
            mod=*this;
        }
        else
        {
        	mod=0;
       	}
    }
    
    return mod;
    
}
BigInteger BigInteger::operator %(long rval)
{
    BigInteger tmp(rval);
    return operator%(tmp);
}
BigInteger BigInteger::operator %(const string &rval)
{
    BigInteger tmp(rval);
    return operator%(tmp);
}
BigInteger & BigInteger::operator %=(const BigInteger &rval)
{
    BigInteger mod=this->operator%(rval);
    this->operator=(mod);
    return *this;
}
BigInteger & BigInteger::operator %=(long rval)
{
    BigInteger mod=this->operator%(rval);
    this->operator=(mod);
    return *this;
}
BigInteger & BigInteger::operator %=(const string &rval)
{
    BigInteger mod=this->operator%(rval);
    this->operator=(mod);
    return *this;
}
BigInteger & BigInteger::operator ++()
{
    *this+=1;
    return *this;
}
BigInteger BigInteger::operator ++(int)
{
    BigInteger tmp(*this);
    *this+=1;
    return tmp;
}
BigInteger & BigInteger::operator --()
{
    *this-=1;
    return *this;
}
BigInteger BigInteger::operator --(int)
{
    BigInteger tmp(*this);
    *this-=1;
    return tmp;
}
bool BigInteger::operator >(const BigInteger &rval)
{
    if(Compare(rval)==1)
        return true;
    else
        return false;
}
bool BigInteger::operator >(long rval)
{
    if(Compare(rval)==1)
        return true;
    else
        return false;
}
bool BigInteger::operator >(const string &rval)
{
    if(Compare(rval)==1)
        return true;
    else
        return false;
}
bool BigInteger::operator <(const BigInteger &rval)
{
    if(Compare(rval)==-1)
        return true;
    else
        return false;
}
bool BigInteger::operator <(long rval)
{
    if(Compare(rval)==-1)
        return true;
    else
        return false;
}
bool BigInteger::operator <(const string &rval)
{
    if(Compare(rval)==-1)
        return true;
    else
        return false;
}
bool BigInteger::operator >=(const BigInteger &rval)
{
    if(Compare(rval)>=0)
        return true;
    else
        return false;
}
bool BigInteger::operator >=(long rval)
{
    if(Compare(rval)>=0)
        return true;
    else
        return false;
}
bool BigInteger::operator >=(const string &rval)
{
    if(Compare(rval)>=0)
        return true;
    else
        return false;
}
bool BigInteger::operator <=(const BigInteger &rval)
{
    if(Compare(rval)<=0)
        return true;
    else
        return false;
}
bool BigInteger::operator <=(long rval)
{
    if(Compare(rval)<=0)
        return true;
    else
        return false;
}
bool BigInteger::operator <=(const string &rval)
{
    if(Compare(rval)<=0)
        return true;
    else
        return false;
}
bool BigInteger::operator ==(const BigInteger &rval)
{
    if(Compare(rval)==0)
        return true;
    else
        return false;
}
bool BigInteger::operator ==(long rval)
{
    if(Compare(rval)==0)
        return true;
    else
        return false;
}
bool BigInteger::operator ==(const string &rval)
{
    if(Compare(rval)==0)
        return true;
    else
        return false;
}
bool BigInteger::operator !=(const BigInteger &rval)
{
    if(Compare(rval)!=0)
        return true;
    else
        return false;
}
bool BigInteger::operator !=(long rval)
{
    if(Compare(rval)!=0)
        return true;
    else
        return false;
}
bool BigInteger::operator !=(const string &rval)
{
    if(Compare(rval)!=0)
        return true;
    else
        return false;
}
ostream & operator<<(ostream &out,const BigInteger &n)
{
    long i=n.length-1;
    out<<n.val[i];
	for(--i;i>=0;--i)
	{	
        out.width(9);
        out.fill('0');
        out<<n.val[i];
    }
    return out;
}
istream & operator>>(istream &in,BigInteger &p)
{
    string str;
    in>>str;
    p=str;
    return in;
}

BigInteger gcd(BigInteger a,BigInteger b)
{
    BigInteger tmp;
    if(a==0)
    	return b;
   	while(a!=0)
   	{
   	    tmp=b%a;
   	    if(tmp==0)
   	    	return a;
   	    else
        {
            a=a%tmp;
            b=tmp;
        }
    }
    return b;
}

int main()
{
    BigInteger a,b,c;
    long testCase;
    cin>>testCase;
    while(testCase-->=1)
    {
        char ch;
        cin>>a>>ch>>b;
        c=gcd(a,b);
        a=a/c;
        b=b/c;
        cout<<a<<" / "<<b<<endl;
    }
}
        

[sumankar]

I had a similar problem, I was sure of the BigInt part, but still got TLE.
And that is when it struck me to tune my input scanning part. I haven't
looked at your BigInt class, call me lazy, if you will! But the input scanning
part -- I did have a look and I do think you need to change it.
It ain't that simple.

HTH

[mf]

sunnycare, I think you have some bugs in your BigInteger.
Try this input:

Code: Select all

1
1000000000000000000000000000000 / 999999999999999999999999999999

[sunnycare]

thanks....you are right ,mf;

but how can you find that? read my code?

i think its more useful for me ...

[dovier_antonio]

I think that your algorithm looks fine...

[Obaida]

This one also got TLE...

Code: Select all

#include<stdio.h>
int main()
{
	long int i,n,a,b,j,pot;
	scanf("%ld",&n);
	{
		for(i=1;i<=n;i++)
		{
			if(b>a)
			{
				pot=a;
				a=b;
				b=pot;
			}
			scanf("%ld / %ld",&a,&b);
			for(j=a;j>=1;j--)
			{
				if(a%j==0&&b%j==0)
				{
					a=a/j;
					b=b/j;
				}
			}
			printf("%ld / %ld\n",a,b);
		}
	}
	return 0;
}

[CSEDU_1323]

hi,
u should read D problem description carefully it says 10^30 which can't b express using even long long u need 2 use BigInt

[sanjoy_nemo]

i've used a class for the BigInts and it's operators but i'm getting WA. can anyone help me with any suggestion or any critical input