HDU 1212(大数求余)

旧城等待， 2022-09-20 11:27 172阅读 0赞

题意：给大数a和b，求a%b

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <algorithm>
    #include <climits>
    #include <cstdlib>
    #include <iomanip>
    #include <cctype>
    using namespace std;
    
    #define MAXN 300 // 可以表示4*MAXN长的十进制数字
    
    class Number
    {
    private:
        static int _t[MAXN];
        static char __t[MAXN*4];
        int* num;
        int len;
        Number(int l, int* t)
        {
            len = l;
            num = new int[len];
            memcpy(num, t, sizeof(int) * len);
        }
        static int getInt(char* t, int n)
        {
            int res = t[0] - '0';
            for (int i = 1; i < n; ++i)
                res = res*10 + t[i]-'0';
            return res;
        }
        static void getNumber(int l, char* t, Number& rhs)
        {
            if (l == 1 && t[0] == '0')
                rhs = Number();
            else
            {
                int i = 0, tt = MAXN;
                while (i < l && t[i] == '0') ++i;
                if (i == l) rhs = Number();
                else
                {
                    while (i < l)
                    {
                        if (i + 4 <= l)
                        {
                            l -= 4;
                            _t[--tt] = getInt(t+l, 4);
                        }
                        else
                        {
                            _t[--tt] = getInt(t+i, l-i);
                            l = i;
                        }
                    }
                    delete[] rhs.num;
                    rhs.len = MAXN - tt;
                    rhs.num = new int[rhs.len];
                    memcpy(rhs.num, _t+tt, sizeof(int)*rhs.len);
                }
            }
        }
    public:
        friend istream& operator>> (istream& in, Number& rhs)
        {
            int i = 0;
            while (in.get(__t[i]))
            {
                if (__t[i] >= '0' && __t[i] <= '9')
                    ++i;
                else if (isspace(__t[i]))
                {
                    if (i)
                    {
                        in.unget();
                        break;
                    }
                }
                else
                {
                    in.unget();
                    if (!i)
                        in.setstate(ios::failbit); 
                    break;
                }
            }
            if (i)
                getNumber(i, __t, rhs);
            return in;
        }
        Number(unsigned int n) 
        { 
            if (n == 0)
            {
                num = new int[1];
                len = 1;
                num[0] = 0;    
                return;
            }
            int t = MAXN;
            while (n > 0)
            {
                _t[--t] = n%10000;
                n /= 10000;
            }
            len = MAXN - t;
            num = new int[len];
            memcpy(num, _t+t, sizeof(int) * len);
        }
        Number() 
        {
            num = new int[1];
            len = 1;
            num[0] = 0;        
        }
        Number operator=(const Number& rhs)
        {
            delete[] num;
            len = rhs.len;
            num = new int[len];
            memcpy(num, rhs.num, sizeof(int) * len);
            return *this;
        }
        Number(const Number& rhs)
        {
            len = rhs.len;
            num = new int[len];
            memcpy(num, rhs.num, sizeof(int) * len);        
        }
        ~Number()
        {
            delete[] num;
        }
        friend ostream& operator<< (ostream& os, const Number& rhs)
        {
            /*
            printf("%d", rhs.num[0]);
            for (int i = 1; i < rhs.len; ++i)
            {
                printf("%04d", rhs.num[i]);
            }
            */
            cout << rhs.num[0];
            for (int i = 1; i < rhs.len; ++i)
            {
                cout << setw(4) << setfill('0') << rhs.num[i];
            }
            return os;
        }
        Number operator/ (const unsigned int n) const
        {
            int i, l = len, carry = 0;
            for (i = 0; i < l; ++i)
            {
                carry = carry*10000+num[i];
                _t[i] = carry/n;
                carry %= n;
            }
            for (i = 0; i < l; ++i)
                if (_t[i]) break;
            if (i == l) i = l-1;
            return Number(l-i, _t+i);
        }
        int operator% (const unsigned int n) const
        {
            int i, l = len, carry = 0;
            for (i = 0; i < l; ++i)
            {
                carry = carry*10000+num[i];
                _t[i] = carry/n;
                carry %= n;
            }
            return carry;
        }
        Number operator* (const unsigned int n) const
        {
            if (n > INT_MAX/10000) 
            {
                cout << "失败:" << n << endl;
                exit(EXIT_FAILURE);
            }
            int t = MAXN, l = len, carry = 0;
            while (l > 0)
            {
                carry += num[--l] * n;
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            while (carry)
            {
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            return Number(MAXN-t, _t+t);
        }
        Number operator+ (const Number& rhs)
        {
            int t = MAXN, l1 = len, l2 = rhs.len, carry = 0;
            while (l1 > 0 && l2 > 0)
            {
                carry += rhs.num[--l2] + num[--l1];
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            while (l2 > 0)
            {
                carry += rhs.num[--l2];
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            while (l1 > 0)
            {
                carry += num[--l1];
                _t[--t] = carry % 10000;
                carry /= 10000;
            }
            if (carry) _t[--t] = carry;
            return Number(MAXN-t, _t+t);
        }
        bool operator== (const Number& rhs) const
        {
            return len == rhs.len && memcmp(num, rhs.num, sizeof(int)*len) == 0;
        }
        friend bool operator== (const unsigned int n, const Number& rhs)
        {
            return rhs.operator== (n);
        }
        friend Number operator+ (const unsigned int n, const Number& rhs)
        {
            return Number(n) + rhs;
        }
        friend Number operator* (const unsigned int n, const Number& rhs)
        {
            return rhs.operator* (n);
        }
    };
    int Number::_t[MAXN];
    char Number::__t[MAXN*4];
    
    int main()
    {
        Number a;
        int b;
        while (cin >> a >> b)
            cout << a%b << endl;
        return 0;
    }