#include "BigInt.h"

BigInt::BigInt(string n){
    s=n;
}

string BigInt::operator+(BigInt ss) {
    return sx(s,ss.s);
}

string BigInt::operator*(BigInt ss) {
    return px(s,ss.s);
}

void BigInt::operator=(string ss) {
    s=ss;
}

string BigInt::operator-(BigInt ss) {
    return dx(s,ss.s);
}

bool BigInt::operator<(BigInt ss) {
    return mai_mic(s,ss.s);
}

string BigInt::sqrt() {
    string rezerve=s;
    string rez,temp,aux,p;
    int ok=0,k,o=0,c=0,l;
    if(s[0]=='-')
        ok=1,s.erase(s.begin()+0);
    if(s.find('.')==-1)
    {
        l=s.size();
        if(s.size()%2)
            k=s.size()/2+1;
        else
            k=s.size()/2;
    }
    else
    {
        k=s.find('.'),s.erase(s.begin()+k);
        l=k;
        if(k%2)
            k=k/2+1;
        else
            k/=2;
    }
    s+="0000000000000000";
    if(l%2)
    {
        o=1;
        temp+=s[0];
        while(c<9)
        {
            aux+=to_string(c++);
            p=px(aux,aux);
            if(!mai_mic_sau_egal(p,temp))
                break;
            aux.pop_back();
        }
        rez+=--aux[0];
        p=dx(temp,px(aux,aux));
        while(p[0]=='0')
            p.erase(p.begin()+0);
        if(p!="")
            temp=p;
        else
            temp="";
    }
    for(int i=o;i<s.size();)
    {
        c=-1;
        temp+=s[i++];
        temp+=s[i++];
        if(temp=="00")
        {
            rez+='0';
            temp="";
            continue;
        }
        if(aux!="")
            aux=px(rez,"2");
        else
        {
            while(c<9)
            {
                c++;
                if(c==10)
                {
                    aux+=to_string(--c);
                    p=px(aux,aux);
                    break;
                }
                else
                    aux+=to_string(c);
                p=px(aux,aux);
                if(!mai_mic_sau_egal(p,temp))
                {
                    if(c==9)
                        c--;
                    break;
                }
                if(c!=9)
                    aux.pop_back();
            }
            if(c==9)
                rez+=to_string(c);
            else
                rez+=--aux[0];
            p=dx(temp,px(aux,aux));
            while(p[0]=='0')
                p.erase(p.begin()+0);
            if(p!="")
                temp=p;
            else
                temp="";
            continue;
        }
        while(c<9)
        {
            c++;
            if(c==10)
            {
                aux+=to_string(--c);
                p=px(aux,to_string(c));
                break;
            }
            else
                aux+=to_string(c);
            p=px(aux,to_string(c));
            if(!mai_mic_sau_egal(p,temp))
            {
                if(c==9)
                    c--;
                break;
            }
            if(c!=9)
                aux.pop_back();
        }
        if(c==9)
            rez+=to_string(c);
        else
            rez+=--aux[aux.size()-1];
        c=aux[aux.size()-1]-'0';
        p=dx(temp,px(aux,to_string(c)));
        while(p[0]=='0')
            p.erase(p.begin()+0);
        if(p!="")
            temp=p;
        else
            temp="";
        if(rez.size()-k>8 && k<rez.size())
            break;
    }
    rez.insert(rez.begin()+k,'.');
    c=rez.find('.');
    while(rez.size()-1-c>8)
        rez.pop_back();
    if(ok)
        rez+='i';
    s=rezerve;
    return rez;
}

string BigInt::sx(string s,string ss) {
    int ls=0,lss=0,o1=0,o2=0,lmax,len;
    if(s.find('.')!=-1)
        ls=s.find('.'),o1=1;
    if(ss.find('.')!=-1)
        lss=ss.find('.'),o2=1;
    lmax=max(ls,lss);
    len=max(s.size(),ss.size());
    if(o1)
    {
        s.erase(s.begin()+ls),ls--;
        ls=s.size()-1-ls;
    }
    if(o2)
    {
        ss.erase(ss.begin()+lss),lss--;
        lss=ss.size()-1-lss;
    }
    len=max(s.size(),ss.size());
    if(ls>lss)
        for(int i=1;i<=ls-lss;i++)
            ss+='0';
    else
    if(lss>ls)
        for(int i=1;i<=lss-ls;i++)
            s+='0';
    int t=0;
    if (s.length()>ss.length())
        swap(s,ss);
    string str="";
    int n1=s.length(),n2=ss.length();
    int dif=n2-n1;
    for(int i=n1-1;i>=0;i--)
    {
        int sum=((s[i]-'0')+(ss[i+dif]-'0')+t);
        str.push_back(sum%10+'0');
        t=sum/10;
    }
    for(int i=n2-n1-1;i>=0;i--)
    {
        int sum=((ss[i]-'0')+t);
        str.push_back(sum%10+'0');
        t=sum/10;
    }
    if(t)
        str.push_back(t+'0');
    reverse(str.begin(),str.end());
    if(ls || lss)
        str.insert(str.begin()+lmax+(str.size()-len),'.');
    return str;
}

string BigInt::dx(string s,string ss) {
    int ls=0,lss=0,o1=0,o2=0,lmax,len;
    if(s.find('.')!=-1)
        ls=s.find('.'),o1=1;
    if(ss.find('.')!=-1)
        lss=ss.find('.'),o2=1;
    lmax=max(ls,lss);
    len=max(s.size(),ss.size());
    if(o1)
    {
        s.erase(s.begin()+ls),ls--;
        ls=s.size()-1-ls;
    }
    if(o2)
    {
        ss.erase(ss.begin()+lss),lss--;
        lss=ss.size()-1-lss;
    }
    len=max(s.size(),ss.size());
    if(ls>lss)
        for(int i=1;i<=ls-lss;i++)
            ss+='0';
    else
    if(lss>ls)
        for(int i=1;i<=lss-ls;i++)
            s+='0';
    int ok=0;
    if(mai_mic_sau_egal(s,ss) && s!=ss)
        swap(s,ss),ok=1;
    string str = "";
    if(s[0]=='0')
        return "0";
    int n1=s.length(),n2=ss.length();
    int dif=n1-n2;
    int t=0;
    for(int i=n2-1;i>=0;i--)
    {
        int sub=((s[i+dif]-'0')-(ss[i]-'0')-t);
        if(sub<0)
            sub+=10,t=1;
        else
            t=0;
        str.push_back(sub+'0');
    }
    for(int i=n1-n2-1;i>=0;i--)
    {
        if(s[i]=='0'&&t)
        {
            str.push_back('9');
            continue;
        }
        int sub=((s[i]-'0')-t);
        if (i>0||sub>0)
            str.push_back(sub+'0');
        t=0;
    }
    reverse(str.begin(),str.end());
    if(ls || lss)
        str.insert(str.begin()+lmax+(str.size()-len),'.');
    while(str[0]=='0' && str.size()>1)
        str.erase(str.begin()+0);
    if(ok)
        str.insert(str.begin()+0,'-');
    return str;
}

string BigInt::px(string s,string ss) {
    int ls=0,lss=0,o1=0,o2=0,ls1=0,ls2=0,lmax;
    if(s.find('.')!=-1)
        ls=s.find('.'),o1=1,ls1=ls;
    if(ss.find('.')!=-1)
        lss=ss.find('.'),o2=1,ls2=lss;
    if(o1)
        ls1=s.size()-1-ls1;
    if(o2)
        ls2=ss.size()-1-ls2;
    lmax=ls1+ls2;
    if(o1)
    {
        s.erase(s.begin()+ls),ls--;
        ls=s.size()-1-ls;
    }
    if(o2)
    {
        ss.erase(ss.begin()+lss),lss--;
        lss=ss.size()-1-lss;
    }
    if(ls>lss)
        for(int i=1;i<=ls-lss;i++)
            ss+='0';
    else
    if(lss>ls)
        for(int i=1;i<=lss-ls;i++)
            s+='0';
    int n1=s.size();
    int n2=ss.size();
    if(n1==0||n2==0)
        return "0";
    vector<int> rez(n1+n2,0);
    int i_n1=0;
    int i_n2=0;
    for(int i=n1-1;i>=0;i--)
    {
        int t=0;
        int n1=s[i]-'0';
        i_n2=0;
        for(int j=n2-1;j>=0;j--)
        {
            int n2=ss[j]-'0';
            int sum=n1*n2+rez[i_n1+i_n2]+t;
            t=sum/10;
            rez[i_n1+i_n2]=sum%10;
            i_n2++;
        }
        if(t>0)
            rez[i_n1+i_n2]+=t;
        i_n1++;
    }
    int i=rez.size()-1;
    while(i>=0 && rez[i]==0)
        i--;
    if(i==-1)
        return "0";
    string sss="";
    while(i>=0)
        sss+=to_string(rez[i--]);
    if(ls1 || ls2)
        sss.insert(sss.begin()+(sss.size()-1-lmax),'.');
    return sss;
}

bool BigInt::mai_mic_sau_egal(string s,string ss) {
    int n1=s.length(),n2=ss.length();
    if(n1<n2)
        return true;
    if(n1>n2)
        return false;

    for(int i=0;i<n1;i++)
    {
        if(s[i]<ss[i])
            return true;
        else
        if(s[i]>ss[i])
            return false;
    }
    return true;
}

void BigInt::operator=(BigInt ss) {
    s=ss.s;
}

pair<string,string> BigInt::ddx(string s, string ss) {
    string rest="0";
    int m=2,ls=0,lss=0,o1=0,o2=0,p1=0,p2=0;
    if(s[0]=='-' || ss[0]=='-')
    {
        m=1;
        if(s[0]=='-' && ss[0]!='-')
            p1=1;
        if(s[0]!='-' && ss[0]=='-')
            p2=1;

    }
    if(s[0]=='-' && ss[0]=='-')
        m=0;
    if(s[0]=='-')
        s.erase(s.begin()+0);
    if(ss[0]=='-')
        ss.erase(ss.begin()+0);
    if(s.find('.')!=-1)
        ls=s.find('.'),o1=1;
    if(ss.find('.')!=-1)
        lss=ss.find('.'),o2=1;
    if(o1)
    {
        s.erase(s.begin()+ls),ls--;
        ls=s.size()-1-ls;
    }
    if(o2)
    {
        ss.erase(ss.begin()+lss),lss--;
        lss=ss.size()-1-lss;
    }
    if(ls>lss)
        for(int i=1;i<=ls-lss;i++)
            ss+='0';
    else
    if(lss>ls)
        for(int i=1;i<=lss-ls;i++)
            s+='0';
    if(ss=="1")
    {
        return make_pair(s+".000000","0");
    }
    if(s=="0")
    {
        return make_pair("0.000000","0");
    }
    string rez;
    if(mai_mic(s,ss))
        rez="0.";
    if(mai_mic(s,ss))
        rest=s;
    while(mai_mic(s,ss))
    {
        s+='0';
        if(!mai_mic(s,ss) || (rez.size()-1-rez.find('.')==6 && rez.find('.')!=-1))
            break;
        rez+='0';
    }
    if(rez.find('.')!=-1)
    {
        if(rez.size()-1-rez.find('.')==6)
            return make_pair(rez,rest);
        else
        if(rez.size()-1-rez.find('.')<6 && rez.find('.')!=-1)
        {
            string temp;
            while(rez.size()-1-rez.find('.')<6)
            {
                int ap=0;
                while(!mai_mic(s,ss))
                    s=dx(s,ss),ap++;
                rez+=to_string(ap);
                s+='0';
            }
            return make_pair(rez,rest);
        }
    }
    string temp;
    int j,k=s.size(),ap=0;
    s+="000000";
    for(int i=0;i<s.size() && mai_mic(temp,ss);i++)
        temp+=s[i],j=i+1;
    while(!mai_mic(temp,ss))
        temp=dx(temp,ss),ap++;
    rez+=to_string(ap);
    for(;j<s.size();j++)
    {
        if(rez.find('.')!=-1 && rez.size()-1-rez.find('.')==6)
        {
            if(m==1)
                rez.insert(rez.begin()+0,'-');
            if(((p1 && !p2) || !m) && rest!="0")
                rest.insert(rest.begin()+0,'-');
            return make_pair(rez,rest);
        }
        ap=0;
        if(j==k)
        {
            rez+='.';
            rest=temp;
            ls=max(ls,lss);
            if(ls)
            {
                rest.insert(rest.begin()+rest.size()-ls,'.');
                if(rest[0]=='.')
                    rest.insert(rest.begin(),'0');
            }
        }
        if(temp[0]=='0')
            temp="",temp+=s[j];
        else
            temp+=s[j];
        if(temp[0]=='0')
        {
            rez+='0';
            continue;
        }
        while(mai_mic(temp,ss) && j<s.size())
        {
            rez+='0',temp+=s[++j];
            if(rez.size()-1-rez.find('.')==6 && rez.find('.')!=-1)
            {
                if(m==1)
                    rez.insert(rez.begin()+0,'-');
                if(((p1 && !p2) || !m) && rest!="0")
                    rest.insert(rest.begin()+0,'-');
                return make_pair(rez,rest);
            }
        }
        while(!mai_mic(temp,ss))
            temp=dx(temp,ss),ap++;
        rez+=to_string(ap);
    }
    if(m==1)
        rez.insert(rez.begin()+0,'-');
    if(((p1 && !p2) || !m) && rest!="0")
        rest.insert(rest.begin()+0,'-');
    return make_pair(rez,rest);
}

pair<string, string> BigInt::operator/(BigInt ss) {
    return ddx(s,ss.s);
}

bool BigInt::mai_mic(string s, string ss) {
    int n1=s.length(),n2=ss.length();
    if(n1<n2)
        return true;
    if(n1>n2)
        return false;

    for(int i=0;i<n1;i++)
    {
        if(s[i]<ss[i])
            return true;
        else
        if(s[i]>ss[i])
            return false;
    }
    return false;
}

bool BigInt::operator<=(BigInt ss) {
    return mai_mic_sau_egal(s,ss.s);
}

bool BigInt::operator==(BigInt ss) {
    return s==ss.s;
}

bool BigInt::mai_mare(string s, string ss) {
    int n1=s.length(),n2=ss.length();
    if(n1<n2)
        return false;
    if(n1>n2)
        return true;

    for(int i=0;i<n1;i++)
    {
        if(s[i]<ss[i])
            return false;
        else
        if(s[i]>ss[i])
            return true;
    }
    return false;
}

bool BigInt::mai_mare_sau_egal(string s, string ss) {
    int n1=s.length(),n2=ss.length();
    if(n1<n2)
        return false;
    if(n1>n2)
        return true;

    for(int i=0;i<n1;i++)
    {
        if(s[i]<ss[i])
            return false;
        else
        if(s[i]>ss[i])
            return true;
    }
    return true;
}

bool BigInt::operator>(BigInt ss) {
    return mai_mare(s,ss.s);
}

bool BigInt::operator>=(BigInt ss) {
    return mai_mare_sau_egal(s,ss.s);
}

string BigInt::pow(string s, string ss) {
    if(ss=="0")
        return "1";
    string rez="1";
    for(string i="1"; mai_mic_sau_egal(i,ss);i=sx(i,"1"))
        rez=px(rez,s);
    return rez;
}

string BigInt::operator^(BigInt ss) {
    return pow(s,ss.s);
}