congruence modulo equations (together with a simple BigInteger class), C++ (gcc)

Language: Layout:

#include<iostream>
#include<vector>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

class BigInteger{ 
    //property 
    private: 
        int sign,d[2000]; 
    public: 
        int length; 
    //method  
    public: 
        BigInteger();//default constructor 
        BigInteger(int);//convert constructor 
        BigInteger(long long int);//convert constructor 
        BigInteger(string);//convert constructor 
        BigInteger(const BigInteger&);//copy constructor 
        //IO stream operation 
        friend ostream& operator << (ostream& ,const BigInteger&); 
        friend istream& operator >> (istream& ,BigInteger&); 
        //assign operation 
        BigInteger& operator =(const BigInteger&); 
        //compare operation 
        friend const bool operator ==(const BigInteger& a,const BigInteger& b){return a.CompareTo(b)==0;} 
        friend const bool operator !=(const BigInteger& a,const BigInteger& b){return a.CompareTo(b)!=0;} 
        friend const bool operator < (const BigInteger& a,const BigInteger& b){return a.CompareTo(b)<0;}         
        friend const bool operator <=(const BigInteger& a,const BigInteger& b){return a.CompareTo(b)<=0;} 
        friend const bool operator > (const BigInteger& a,const BigInteger& b){return a.CompareTo(b)>0;} 
        friend const bool operator >=(const BigInteger& a,const BigInteger& b){return a.CompareTo(b)>=0;} 
        //bit operation 
        const BigInteger operator <<  (const int&); 
        const BigInteger operator >>  (const int&); 
        const BigInteger operator <<= (const int& k){return *this=*this<<k;} 
        const BigInteger operator >>= (const int& k){return *this=*this>>k;} 
        //arithmetic operation 
        friend const BigInteger operator + (const BigInteger&,const BigInteger&); 
        friend const BigInteger operator - (const BigInteger&,const BigInteger&);       
        friend const BigInteger operator * (const BigInteger&,const BigInteger&); 
        friend const BigInteger operator / (const BigInteger&,const BigInteger&); 
        friend const BigInteger operator % (const BigInteger&,const BigInteger&); 
        friend const BigInteger operator +=(BigInteger& a,const BigInteger& b){return a=a+b;} 
        friend const BigInteger operator -=(BigInteger& a,const BigInteger& b){return a=a-b;} 
        friend const BigInteger operator *=(BigInteger& a,const BigInteger& b){return a=a*b;} 
        friend const BigInteger operator /=(BigInteger& a,const BigInteger& b){return a=a/b;} 
        friend const BigInteger operator %=(BigInteger& a,const BigInteger& b){return a=a%b;} 
        //other operator 
        const BigInteger operator -  () const; 
        const BigInteger operator ++ (){return *this=*this+1;} 
        const BigInteger operator -- (){return *this=*this-1;} 
        const BigInteger operator ++ (int){BigInteger tmp=*this;++*this;return tmp;} 
        const BigInteger operator -- (int){BigInteger tmp=*this;--*this;return tmp;} 
        int& operator [] (const int &x){return d[x];}//access d directly 
        const int operator [] (const int &x) const {return d[x];} 
        friend const BigInteger abs(const BigInteger& x){return x<0?-x:x;}; 
    private: 
        const int CompareTo(const BigInteger&) const; 
        const BigInteger unsigned_plus(const BigInteger&) const; 
        const BigInteger unsigned_minus(const BigInteger&) const;        
        const BigInteger unsigned_mult(const BigInteger&) const; 
        const BigInteger unsigned_divide(const BigInteger&,bool) const; 
}; 
BigInteger::BigInteger(){memset(d,0,sizeof(d));sign=length=1;} 
BigInteger::BigInteger(int x){ 
    memset(d,0,sizeof(d)); 
    sign=x>=0?1:-1,length=x?0:1,x=x<0?-x:x; 
    for(unsigned int i=0;x;++i,++length)d[i]=x%10,x/=10; 
} 
BigInteger::BigInteger(long long int x){ 
    memset(d,0,sizeof(d)); 
    sign=x>=0?1:-1,length=x?0:1,x=x<0?-x:x; 
    for(unsigned int i=0;x;++i,++length)d[i]=x%10,x/=10; 
} 
BigInteger::BigInteger(string s){ 
    memset(d,0,sizeof(d)); 
    if(s[0]=='-')sign=-1,s.erase(0,1); 
    else if(s[0]=='+')sign=1,s.erase(0,1); 
    else sign=1; 
    length=s.length(); 
    reverse(s.begin(),s.end()); 
    for(unsigned int i=0;i<s.length();++i)d[i]=s[i]-'0'; 
    while(length>1 && !d[length-1])--length; 
    if(length==1 && d[0]==0)sign=1; 
} 
BigInteger::BigInteger(const BigInteger &x){ 
    memset(d,0,sizeof(d)); 
    sign=x.sign; 
    length=x.length; 
    for(int i=0;i<length;++i)d[i]=x.d[i]; 
} 
BigInteger& BigInteger::operator=(const BigInteger &x){ 
    if(this == &x) return *this; 
    memset(d,0,sizeof(d)); 
    sign=x.sign; 
    length=x.length; 
    for(int i=0;i<length;++i)d[i]=x.d[i]; 
    return *this; 
} 
ostream& operator << (ostream &os,const BigInteger &x){ 
    if(x.sign<0)os<<'-'; 
    for(int i=x.length-1;i>=0;--i)os<<x.d[i]; 
    return os; 
} 
istream& operator >> (istream &is,BigInteger &x){ 
    string s; 
    cin>>s;x=s; 
    return is; 
} 
const BigInteger BigInteger::operator <<  (const int&k){ 
    //We temporarily let the multiplication pretend to be left-shift operation. 
    //So the computational complexity is the same as multiplication operation. 
    //It is just provided to remain compliant with the bit operation of int.  
    int w=1; 
    for(int i=0;i<k;++i)w<<=1; 
    return (*this)*w; 
} 
const BigInteger BigInteger::operator >>  (const int&k){ 
    //For the same reason,we divide operation for right-shift operation. 
    int w=1; 
    for(int i=0;i<k;++i)w<<=1; 
    return (*this)/w; 
} 
const BigInteger operator + (const BigInteger &a,const BigInteger &b){ 
    BigInteger ret,x=abs(a),y=abs(b); 
    if(a.sign^b.sign){ 
        if(x<y)ret=y.unsigned_minus(x),ret.sign=b.sign; 
        else if(x>y)ret=x.unsigned_minus(y),ret.sign=a.sign; 
    }else ret=x.unsigned_plus(y),ret.sign=a.sign; 
    return ret; 
} 
const BigInteger operator - (const BigInteger &a,const BigInteger &b){ 
    return a+(-b); 
} 
const BigInteger operator * (const BigInteger &a,const BigInteger &b){ 
    BigInteger ret,x=abs(a),y=abs(b);  
    ret=x.unsigned_mult(y); 
    if(ret.length==1 && ret[0]==0)ret.sign=1; 
    else ret.sign=(a.sign^b.sign)?-1:1; 
    return ret; 
} 
const BigInteger operator / (const BigInteger &a,const BigInteger &b){ 
    BigInteger ret=0,x=abs(a),y=abs(b); 
    if(y==0)cout<<"Divide By Zero!"<<endl; 
    else ret=x.unsigned_divide(y,true),ret.sign=(a.sign^b.sign)?-1:1; 
    if(ret.length==1 && ret[0]==0)ret.sign=1; 
    return ret; 
} 
const BigInteger operator % (const BigInteger &a,const BigInteger &b){ 
    BigInteger ret=0,x=abs(a),y=abs(b); 
    if(y==0)cout<<"Divide By Zero!"<<endl; 
    else ret=x.unsigned_divide(y,false),ret.sign=a.sign; 
    if(ret.length==1 && ret[0]==0)ret.sign=1; 
    return ret; 
} 
const BigInteger BigInteger::operator -() const{ 
    BigInteger temp=*this; 
    temp.sign=-this->sign; 
    return temp; 
} 
const int BigInteger::CompareTo(const BigInteger &x) const{ 
    if(sign>x.sign) return 1; 
    if(sign<x.sign) return -1; 
    if(length>x.length)return sign; 
    if(length<x.length)return -sign; 
    for(int i=length-1;i>=0;--i){ 
        if(d[i]>x[i])return sign; 
        if(d[i]<x[i])return -sign; 
    } 
    return 0; 
} 
const BigInteger BigInteger::unsigned_plus(const BigInteger &x) const{ 
    BigInteger ret; 
    ret.length=length; 
    if(ret.length<x.length)ret.length=x.length; 
    int i,carry=0; 
    for(i=0;i<ret.length;++i){ 
        ret[i]+=d[i]+x[i]+carry; 
        carry=ret[i]/10,ret[i]%=10; 
    } 
    if(carry)ret[i]+=carry,++ret.length; 
    return ret; 
} 
const BigInteger BigInteger::unsigned_minus(const BigInteger &x) const{ 
    BigInteger ret; 
    ret.length=length;//suppose a > b  
    for(int i=0;i<length;++i){ 
        ret[i]+=d[i]-x[i]; 
        if(ret[i]<0)ret[i]+=10,--ret[i+1]; 
    } 
    while(ret.length>1 && !ret[ret.length-1])--ret.length; 
    return ret; 
} 
const BigInteger BigInteger::unsigned_mult(const BigInteger &x) const{ 
    BigInteger ret;  
    int i=0,j=0; 
    for(i=0;i<length;++i){ 
        int carry=0; 
        for(j=0;j<x.length;++j){    
            ret[i+j]+=d[i]*x[j]+carry; 
            carry=ret[i+j]/10,ret[i+j]%=10;   
        } 
        if(carry)ret[i+j]+=carry;    
    } 
    ret.length=i+j; 
    while(ret.length>1 && !ret[ret.length-1])--ret.length; 
    return ret; 
} 
const BigInteger BigInteger::unsigned_divide(const BigInteger &x,bool type) const{ 
    BigInteger div,mod; 
    div.length=length,mod.length=1; 
    for(int i=length-1;i>=0;--i){ 
        mod*=10,mod[0]=d[i]; 
        while(mod>=x)mod-=x,++div[i]; 
    } 
    while(div.length>1 && !div[div.length-1])--div.length; 
    return type?div:mod; 
}

struct Equation{
	BigInteger a,m;  // x= a mod m
	Equation(BigInteger _a, BigInteger _m){
		if(0!=_m){
			a=(_a%_m+_m)%_m;
			m=_m;
		}else{
			a=m=0;
		}
	};
};

BigInteger exgcd(BigInteger a,BigInteger b,BigInteger &x,BigInteger &y){
    if(0==b) {
        x=1, y=0;
		return a; 
    }
    BigInteger d=exgcd(b,a%b,y,x); 
    y-=a/b*x;
	return d;
}

Equation solve(vector<Equation> eq){
    Equation eq1=eq[0];
    for(unsigned int i=1;i<eq.size();i++){
        Equation eq2=eq[i];
        BigInteger c=eq2.a-eq1.a;
        BigInteger q1,q2;
        BigInteger d=exgcd(eq1.m,eq2.m,q1,q2); // m1*q1+m2*q2=gcd(m1,m2)
        if(0!=c%d){
            return Equation(0, 0);
        }
		eq1=Equation(c/d*q1*eq1.m+eq1.a,eq2.m/d*eq1.m);
    }
    return eq1;
}

int main() {
	vector<vector<Equation> > test;
    vector<Equation> eq;
    // test case 1
	eq.push_back(Equation(5,9));
	eq.push_back(Equation(7,13));
	eq.push_back(Equation(2,15));
	eq.push_back(Equation(3,17));
	eq.push_back(Equation(47,57));
	//eq.push_back(Equation(998,999));
	test.push_back(eq);
    eq.clear();
    // test case 2
    eq.push_back(Equation(233224LL,12322234LL));
	eq.push_back(Equation(234,2345));
    test.push_back(eq);
    eq.clear();
    // test case 3
    eq.push_back(Equation(233224LL,12322234LL));
	eq.push_back(Equation(53452344LL,100234244LL));
    test.push_back(eq);
    eq.clear();
    // test case 4
    eq.push_back(Equation(23322434LL,12322234234LL));
	eq.push_back(Equation(234,2345));
    test.push_back(eq);
    eq.clear();
    // test case 5
	eq.push_back(Equation(233224334LL,12322234234LL));
	eq.push_back(Equation(234LL,2345LL));
    test.push_back(eq);
    eq.clear();
    // test case 6
    eq.push_back(Equation(111,123));
	eq.push_back(Equation(2,6));
    test.push_back(eq);
    eq.clear();
    
    for(unsigned int i=0;i<test.size();i++){
        cout<<"Test Case "<<i+1<<":"<<endl;
        vector<Equation> eq=test[i];
        for(unsigned int j=0;j<eq.size();j++){
            cout<<"| x = "<<eq[j].m<<" * t"<<j+1<<" + "<<(eq[j].a)<<endl;
        }
        Equation result=solve(eq);
        if(result.a==0 && result.m==0){
            cout<<"No solution!"<<endl;
        }else{
            cout<<"Solution: x = "<<result.m<<"t + "<<result.a<<", t=0,1,2,..."<<endl;
        }
        cout<<endl;
    }
	return 0;
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 1.12 sec, absolute running time: 0.1 sec, cpu time: 0.06 sec, memory peak: 3 Mb, absolute service time: 1,25 sec