BigInteger Library

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <vector>
#include <iostream>
#include <complex>
using namespace std;

#define BIT 10009
#define GRP     5
#define RADIX   100000  // 10^GRP

typedef complex<long double> Complex;
long double PI = 2 * acos(0.0L);

unsigned revtab[65536];
char fin[4000000];
void init()
{
    for (int x = 0; x < 65536; x++)
    {
        int y = 0;for (int i = 0; i < 16; i++)y |= ((x >> i) & 1) << (15 - i);revtab[x] = y;
    }
}

void FFT(Complex *a, int N, int dir)
{
    int lgN;for (lgN = 1; (1 << lgN) < N; lgN++);assert((1 << lgN) == N);
    for (unsigned i = 0; i < N; i++)
    {
        unsigned j = ((revtab[i & 65535] << 16) | revtab[i >> 16]) >> (32 - lgN);if (i < j) swap(a[i], a[j]);
    }
    for (int s = 1; s <= lgN; s++)
    {
        int m = 1 << s, h = m/2;Complex w, w_m = exp(Complex(0, dir*2*PI/m));
        for (int k = 0; k < N; k += m)
        {
            // even=a[k..k+n), odd=a[k+n..k+m)
            w = 1;
            for (int j = 0; j < h; j++)
            {
                Complex t = w * a[k+h+j];a[k+h+j] = a[k+j] - t;a[k+j] += t;w *= w_m;
            }
        }
    }
}
void parse(vector<Complex> &v, const char *s)
{
    int n = strlen(s);int m = (n + GRP-1) / GRP;v.resize(m);
    for (int i = 0; i < m; i++)
    {
        int b = n - GRP * i, x = 0;for (int a = max(0, b - GRP); a < b; a++)x = x * 10 + s[a] - '0';v[i] = x;
    }
}
void Extract(const vector<Complex> &v,int signa,int signb)
{
    cout << signa << " ->>>> " << signb << endl;
    int i, N = v.size();
    vector<long long> digits(N + 1, 0);
    long double err = 0;
    for (i = 0; i < N; i++)
    {
        long long x = (long long)(v[i].real() + 0.5);err = max(err, abs(x - v[i].real()));err = max(err, abs(v[i].imag()));digits[i] = x;
    }
    long long c = 0;
    for (i = 0; i < N; i++)
    {
        c += digits[i];digits[i] = c % RADIX;c /= RADIX;
    }
    assert(c == 0);
    for (i = N-1; i > 0 && digits[i] == 0; i--);int idx=0,blen=0;char buff[30];
    sprintf(buff,"%lld", digits[i]);if(signa!=signb)fin[idx++]='-';while(buff[blen]!='\0')fin[idx++]=buff[blen++];
    for (i--; i >= 0; i--)
    {
        sprintf(buff,"%.*lld", GRP, digits[i]);blen=0;while(buff[blen]!='\0')fin[idx++]=buff[blen++];
    }
    fin[idx]='\0';
    //cout << "##" << fin << endl;
}
void mul(string &xx,string &yy,int signa,int signb)
{
    vector<Complex> A, B;
    parse(A, xx.c_str());parse(B, yy.c_str());int N = 1;
    while (N < max(A.size(), B.size())) N *= 2;N *= 2;A.resize(N);B.resize(N);FFT(&A[0], N, +1);FFT(&B[0], N, +1);for (int i = 0; i < N; i++) A[i] *= B[i];
    FFT(&A[0], N, -1);for (int i = 0; i < N; i++) A[i] /= N;Extract(A,signa,signb);
}
template<class T> string toString(T n)
{
    ostringstream ost;ost << n;ost.flush();return ost.str();
}
struct Bigint
{
    // representations and structures
    string a; // to store the digits
    int sign; // sign = -1 for negative numbers, sign = 1 otherwise
    void getInt()
    {
        a.clear();char ch;
        while(true)
        {
            ch=getchar();if(ch=='\n' || ch==' ')break;a.push_back(ch);
        }
        (*this) = a;
    }
    // constructors
    Bigint() {} // default constructor
    Bigint( string b ){(*this) = b;}    // constructor for string
    // some helpful methods
    int size(){return a.size();}// returns number of digits
    Bigint inverseSign() {sign *= -1;return (*this);}
    // changes the sign
    Bigint normalize( int newSign )   // removes leading 0, fixes sign
    {
        //cout << this->a << " <.> "<< endl;
        for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- )a.erase(a.begin() + i);sign = ( a.size() == 1 && a[0] == '0' ) ? 1 : newSign;
        //reverse( a.begin(), a.end() );
        return (*this);
    }
    void operator = ( int b )
    {
        (*this)=toString(b);
    }
    // assignment operator
    void operator = ( string b )
    {
        a = b[0] == '-' ? b.substr(1) : b;reverse( a.begin(), a.end() );this->normalize( b[0] == '-' ? -1 : 1 );
        //a.
    }
    // conditional operators
    bool operator < ( const Bigint &b ) const   // less than operator
    {

        if( sign != b.sign ) return sign < b.sign;
        if( a.size() != b.a.size() )return sign == 1 ? a.size() < b.a.size() : a.size() > b.a.size();
        for( int i = a.size() - 1; i >= 0; i-- ) if( a[i] != b.a[i] )return sign == 1 ? a[i] < b.a[i] : a[i] > b.a[i];
        return false;
    }
    bool operator < ( const int &b ) const
    {
        return (*this) < toString(b);
    }
    bool operator == ( const Bigint &b ) const   // operator for equality
    {
        return a == b.a && sign == b.sign;
    }
    bool operator == ( const long long &b ) const
    {
        return (*this) == toString(b);
    }
// mathematical operators
    Bigint operator + ( Bigint b )   // addition operator overloading
    {
        if( sign != b.sign ) return (*this) - b.inverseSign();
        Bigint c;
        for(int i = 0, carry = 0; i<a.size() || i<b.size() || carry; i++ )
        {
            carry+=(i<a.size() ? a[i]-48 : 0)+(i<b.a.size() ? b.a[i]-48 : 0);
            c.a += (carry % 10 + 48);
            carry /= 10;
        }
        return c.normalize(sign);
    }
    Bigint operator + ( long long b ){return (*this) + toString(b);}
    Bigint operator - ( Bigint b )   // subtraction operator overloading
    {
        if( sign != b.sign ) return (*this) + b.inverseSign();
        int s = sign;
        sign = b.sign = 1;
        if( (*this) < b ) return ((b - (*this)).inverseSign()).normalize(-s);
        Bigint c;
        for( int i = 0, borrow = 0; i < a.size(); i++ )
        {
            borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
            c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
            borrow = borrow >= 0 ? 0 : 1;
        }
        return c.normalize(s);
    }
    Bigint operator - ( long long  b ){return (*this) - toString(b);}
    Bigint operator * ( Bigint b )   // multiplication operator overloading
    {
        reverse( a.begin(), a.end() );
        reverse( b.a.begin(), b.a.end() );
        //int u=0,uu=0;
        //if( a[0]=='-')u=1,a=a.substr(1);
        //else if(a[0]=='+') a=a.substr(1);
        //if( b.a[0]=='-')uu=1, b.a=b.a.substr(1);
        //else if(a[0]=='+')b.a=b.a.substr(1);
        mul(a,b.a,this->sign,b.sign);
        reverse( a.begin(), a.end() );
        reverse( b.a.begin(), b.a.end() );
        return Bigint((string)fin);
    }
    Bigint operator * ( long long b ){return (*this) * toString(b);}

    Bigint operator / ( Bigint b )   // division operator overloading BI/BI
    {
        if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );Bigint c("0"), d;
        for( int j = 0; j < a.size(); j++ ) d.a += "0";int dSign = sign * b.sign;b.sign = 1;
        for( int i = a.size() - 1; i >= 0; i-- )
        {
            c.a.insert( c.a.begin(), '0');c = c + a.substr( i, 1 );while( !( c < b ) ) c = c - b, d.a[i]++;
        }
        return d.normalize(dSign);
    }
    Bigint operator / ( long long n )   // division operator overloading BI/BI
    {
        reverse( a.begin(), a.end() );
        //reverse( b.begin(), b.end() );
        long long int rem=0,i,j=0;int f=1;int idx=0;int len=a.length();
        for(i=0; i<len; i++)
        {
            rem=a[i]-'0'+rem*10;
            if(rem/n!=0)f=0;
            if(f==0)fin[idx++]=((char)((rem/n)+'0'));
            rem=rem%n;
        }
        if(f==1)fin[idx++]='0';fin[idx]='\0';
        reverse( a.begin(), a.end() );
        //reverse( b.begin(), b.end() );
        return Bigint((string)fin);
    }
    Bigint operator % ( Bigint b )   // modulo operator overloading
    {
        if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );
        Bigint c("0");b.sign = 1;
        for( int i = a.size() - 1; i >= 0; i-- )
        {
            c.a.insert( c.a.begin(), '0');c = c + a.substr( i, 1 );while( !( c < b ) ) c = c - b;
        }
        return c.normalize(sign);
    }
    Bigint operator % ( long long n )   // modulo operator overloading
    {
        reverse( a.begin(), a.end() );
        //reverse( b.begin(), b.end() );
        long long int i,rem=0,j;
        int idx=0;int len=a.length();
        for(i=0; i<len; i++)
        {
            rem=a[i]-'0'+rem*10;rem=rem%n;
        }
        reverse( a.begin(), a.end() );
        //reverse( b.begin(), b.end() );
        return Bigint(toString(rem));
    }
    void print()
    {
        if( sign == -1 ) putchar('-');
        for( int i = a.size() - 1; i >= 0; i-- ) putchar(a[i]);
    }
    Bigint sqrt()
    {
        reverse( this->a.begin(), this->a.end() );
        //reverse( b.begin(), b.end() );
        string a=this->a;int idx=0;int n = a.size();bool f = n%2;n = (f)?n+1:n;vector <int> num (n, 0);int i;
        if (f)for (i = 0; i < n-1; i++)num[i+1] = a[i] - 48;
        else for (i = 0; i < n; i++)num[i] = a[i] - 48;
        n /= 2;
        vector <int> root(n, 0);vector <int> recieve;
        for (i = 0; i < n; i++)
        {
            recieve.push_back (num[i*2]);
            recieve.push_back(num[i*2+1]);
            vector <int> cand(i+1, 0);
            int tmp, ac = 0;
            for (int j = i; j > 0; j--)
            {
                tmp = root[j-1]*2 + ac;
                cand[j] = tmp%10;
                ac = tmp/10;
            }
            if (ac) cand[0] += ac;
            int j;
            for (j = 9; j >= 0; j--)
            {
                int l = 2*(i+1);
                vector <int>  m (l, 0);
                m[l-1] = j*j;m[l-2] = m[l-1]/10;m[l-1] %= 10;
                int k, o;int ac = 0;
                for (k = l-2, o = i; o >= 0 && k > 0; k--, o--)
                {
                    m[k] += cand[o]*j;m[k-1] = m[k]/10;m[k] %= 10;
                }
                bool flag = 1;
                for (k = 0; k < l; k++)
                {
                    if (recieve[k] > m[k]) break;
                    if (recieve[k] < m[k])
                    {
                        flag = 0;
                        break;
                    }
                }
                if (flag)
                {
                    ac = 0;
                    for (k = l-1; k >= 0; k--)
                    {
                        tmp = recieve[k] - m[k] - ac;
                        if (tmp < 0)
                        {
                            recieve[k] = tmp+10;ac = 1;
                        }
                        else
                        {
                            recieve[k] = tmp;ac = 0;
                        }
                    }
                    break;
                }
            }
            root[i] = j;fin[idx++]=(j+'0');
        }
        fin[idx]='\0';
        reverse( this->a.begin(),this->a.end() );
        //reverse( b.begin(), b.end() );
        return Bigint(string(fin));
    }
};
istream& operator >> (istream &in, Bigint &x)
{
    in >> x.a;
    x=Bigint(x.a);
    return in;
}
ostream& operator << (ostream &out, const Bigint &x)
{
    string p=x.a;
    reverse(p.begin(),p.end());
    if(x.sign==-1)p="-"+p;
    out << p;
    return out;
}
char inp[BIT];
int main()
{
    Bigint A,B,C,D;
    A.getInt();//character by character read.needs to care about extra spaces/newlines
    cin >> B;//string
    cout << A/B << endl;

    C="-100";
    D=-400LL;
    cout << A << " " << B << " " << C << " " << D << endl;
    cout << A.sign << " " << B.sign << " " << C.sign << " " << D.sign << endl;
    if(A==B)cout << "A equals to B\n";
    else if(A<B)cout << "A is less than B\n";
    else cout << "A is greater than B\n";

    cout << "A+B" << " " << A+B << endl;
    cout << "A-B" << " " << A-B << endl;
    cout << "A*B" << " " << A*B << endl;
    cout << "A/B" << " " << A/B << endl;


    cout << A.sqrt() << endl;
    cout << A << " " << B << " " << A+B << " " << C << " " << (A+B)/C << endl;
    cout << A%B << endl;

    cout << A+B/C << endl;
    cout << A%50 << endl;

    int INT=50;
    cout << B%INT << endl;

    if(A<10)cout << "A is less than 10\n";
    if(A+15<25)cout << A << " + 15 is less than 25" << endl;

    cout << A+17 << " " << A-19 << endl;

    return 0;
}