2015年1月29日 星期四

2015/01/29 ZJ a021: 大數運算

// http://zerojudge.tw/ShowProblem?problemid=a021
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

struct ll
{
    #define now (*this)

    int num[1001];
    static const int n = 1000;

    int& operator[](int x){ return num[x]; }

    static void fix(ll &p)
    {
        for(int i = 0; i < n; i++)
        {
            if( p[i] >= 10 )
            {
                p[i+1] += p[i]/10;
                p[i] %= 10;
            }

            if( p[i] < 0 )
            {
                p[i] += 10;
                p[i+1]--;
            }
        }
    }

    static int up(ll &p)
    {
        for(int i = n; i >= 0; i--)
            if( p[i] != 0 ) return i;

        return 0;
    }

    ll(){ fill(num, num+1001, 0); }
    ll(int x)
    {
        char *c = new char[1000];
        sprintf(c, "%d", x);

        now = ll(c);
    }
    ll(char *c)
    {
        now = ll();
        int cn = strlen(c);

        for(int ci = 0; ci < cn; ci++)
            now[cn-1-ci] = c[ci]-'0';
    }

    bool operator<(ll p)
    {
        for(int ni = n; ni >= 0; ni--)
        {
            if( now[ni] < p[ni] ) return true;
            if( now[ni] > p[ni] ) return false;
        }

        return false;
    }

    ll operator+(ll p)
    {
        ll re = ll();

        for(int i = 0; i <= n; i++)
            re[i] = p[i]+now[i];

        fix(re);

        return re;
    }

    ll operator-(ll p)
    {
        ll re = ll();

        for(int i = 0; i <= n; i++)
            re[i] = now[i]-p[i];

        fix(re);

        return re;
    }

    ll operator*(ll p)
    {
        int cnt = 0;
        ll x, y;

        if( now[n] == -1 )
        {
            cnt++;
            x = ll(1)-now;
        }
        else x = now;

        if( p[n] == -1 )
        {
            cnt++;
            y = ll(1)-p;
        }
        else y = p;

        ll re = ll();

        for(int xi = 0, xn = up(x); xi <= xn; xi++)
            for(int yi = 0, yn = up(y); yi <= yn; yi++)
                re[xi+yi] += now[xi]*p[yi];

        fix(re);

        return re;
    }

    ll operator/(ll p)
    {
        ll re = ll();

        int m = up(now);

        for(int mi = m; mi >= 0; mi--)
        {
            for(int i = 1; i <= 9; i++)
            {
                re[mi] = i;
                if( now < re*p ) break;
            }

            re[mi]--;
        }

        return re;
    }

    char* c_str()
    {

        char *c = new char[1000];

        if( now[n] == -1 )
        {
            strcpy(c+1, ll(ll(0)-now).c_str());
            c[0] = '-';
            return c;
        }

        int cn = up(now);

        for(int ci = 0; ci <= cn; ci++)
            c[ci] = now[cn-ci]+'0';

        c[cn+1] = '\0';
        return c;
    }
};

char a[1000], b[1000]; char c;

int main()
{
    while( scanf(" %[0-9] %c %[0-9]", a, &c, b) != EOF )
    {
        if( c == '+' ) cout<<((ll)a+b ).c_str()<<endl;
        if( c == '-' ) cout<<((ll)a-b ).c_str()<<endl;
        if( c == '*' ) cout<<((ll)a*b ).c_str()<<endl;
        if( c == '/' ) cout<<((ll)a/b ).c_str()<<endl;
    }
}

沒有留言:

張貼留言