c + + 대수 클래스

#include 
#include 
#include 
#include 
#define LL long long
#define INF 0x3f3f3f3f

using namespace std;
const int M = 1e3+10;
const int MAXN = 9;
class BigNum {
    public:
        int a[M],len,sign;
        void init();
        void assignString(const char*);
        void assignInt(LL);
        LL toInt()const;

        BigNum();
        BigNum(LL);//int -> BigNum
        BigNum(const char*);//char -> BigNum
        BigNum(const BigNum &); //BigNum = BigNum

        BigNum &operator = (const BigNum &);
        friend istream& operator>>(istream&,BigNum&);
        friend ostream& operator< (const BigNum&)const;
        bool operator < (const BigNum&)const;

        BigNum operator + (const LL&)const;//all
        BigNum operator - (const LL&)const;//all
        BigNum operator * (const LL&)const;//all
        BigNum operator / (const LL&)const;//LL != 0 && BigNum all
        BigNum operator ^ (const LL&)const;//LL >= 0 && BigNum >= 0
        LL operator % (const LL&)const;//BigNum >=0 && LL > 0
};
void BigNum::init() {
    len = 0;
    sign = 1;
    memset(a,0,sizeof(a));
}
void BigNum::assignString(const char *s) {
    init();
    int l = strlen(s);
    int k = 0;
    if(s[0] == '-') {
        sign = -1;
        k++;
    }
    int j = 0;
    for(LL seed = 1; seed < MAXN; seed *= 10,j++) ;
    bool flag = false;
    for(int i = l-1; i >= k; i -= j) {
        for(int jj = max(i-j+1,k); jj <= i; ++jj) {
            a[len] = a[len]*10+(s[jj]-'0');
        }
        len++;
        if(a[len-1] != 0) {
            flag = true;
        }
    }
    if(!flag) {
        sign = 1;
        len = 1;
    }
}
void BigNum::assignInt(LL b) {
    init();
    if(b == 0) {
        len = 1;
        return ;
    }
    if(b < 0) {
        sign = -1;
        b = -b;
    }
    while(b) {
        a[len++] = b%(MAXN+1);
        b /= (MAXN+1);
    }
}
LL BigNum::toInt() const{
    LL res = 0,seed = 1;
    for(int i = len-1; i >= 0; --i) {
        res += seed*res+a[i];
        seed *= (MAXN+1);
    }
    if(sign == -1) res = -res;
    return res;
}
BigNum::BigNum() {
    init();
    len = 1;
}
BigNum::BigNum(LL b) {
    assignInt(b);
}
BigNum::BigNum(const char* s) {
    assignString(s);
}
BigNum::BigNum(const BigNum& t){
    *this = t;
}

BigNum & BigNum::operator = (const BigNum & t) {
    init();
    len = t.len;
    sign = t.sign;
    for(int i = 0; i < t.len; ++i) {
        a[i] = t.a[i];
    }
    return *this;
}
istream& operator >> (istream& in,BigNum &t) {
    char s[M];
    in>>s;
    t.assignString(s);
    return in;
}
ostream& operator << (ostream& ou,BigNum &t) {
    if(t.sign == -1){
        ou<= 0; --i) {
        ou.width(j);
        ou.fill('0');
        ou< len ? t.len : len;
        for(int i = 0; i < big; ++i) {
            res.a[i] += t.a[i];
            if(res.a[i] > MAXN) {
                res.a[i+1]++;
                res.a[i] -= MAXN+1;
            }
        }
        if(res.a[big] != 0) {
            res.len = big+1;
        }
        else {
            res.len = big;
        }
    }
    else if(sign == 1 && t.sign == -1) {
        BigNum tmp(t);
        tmp.sign = 1;
        res = *this-tmp;
    }
    else {
        BigNum tmp(*this);
        tmp.sign = 1;
        res = t-tmp;
    }
    return res;
}
BigNum BigNum::operator - (const BigNum &t)const {
    BigNum res;
    if(sign == t.sign && sign == 1) {
        BigNum t1,t2;
        if(*this < t) {
            t1 = t;
            t2 = *this;
            t1.sign = -1;
        }else {
            t1 = *this;
            t2 = t;
        }
        int big = t1.len;
        for(int i = 0; i < big; ++i) {
            if(t1.a[i] < t2.a[i]) {
                int j = i+1;
                while(t1.a[j] == 0) {
                    j++;
                }
                t1.a[j--]--;
                while(j > i) {
                    t1.a[j] += MAXN;
                }
                t1.a[i] += MAXN+1-t2.a[i];
            }
            else {
                t1.a[i] -= t2.a[i];
            }
        }
        while(t1.a[t1.len-1] == 0 && t1.len > 1) {
            t1.len--;
        }
        if(t1.len == 1 && t1.a[0] == 0){
            t1.sign = 1;
        }
        res = t1;
    }
    else if(sign == t.sign && sign == -1){
        BigNum t1,t2;
        t1 = t;
        t2 = *this;
        t1.sign = t2.sign = 1;
        res = t1-t2;
    }
    else if(sign == 1 && t.sign == -1) {
        BigNum t1,t2;
        t1 = *this;
        t2 = t;
        t2.sign = 1;
        res = t1+t2;
    }
    else if(sign == -1 && t.sign == 1) {
        BigNum t1,t2;
        t1 = *this;
        t2 = t;
        t2.sign = -1;
        res = t1+t2;
    }
    return res;
}
BigNum BigNum::operator * (const BigNum &t)const {
    BigNum res;
    res.sign = sign*t.sign;
    int i,j;
    for(i = 0; i < len; ++i) {
        int up = 0;
        for(j = 0; j < t.len; ++j) {
            int tmp = a[i]*t.a[j]+res.a[i+j]+up;
            if(tmp > MAXN) {
                int tmp1 = tmp - tmp/(MAXN+1)*(MAXN+1);
                up = tmp / (MAXN+1);
                res.a[i+j] = tmp1;
            }else {
                up = 0;
                res.a[i+j] = tmp;
            }
        }
        if(up != 0) {
            res.a[i+j] = up;
        }
    }
    res.len = i+j;
    while(res.a[res.len-1] == 0 && res.len > 1) {
        res.len--;
    }
    if(res.len == 1 && res.a[0] == 0){
            res.sign = 1;
    }
    return res;
}
BigNum BigNum::operator / (const BigNum &t)const {
    LL b = t.toInt();
    BigNum res = *this/b;
    return res;
}

BigNum BigNum::operator + (const LL& b)const {
    BigNum t(b);
    BigNum res = *this+t;
    return res;
}
BigNum BigNum::operator - (const LL& b)const {
    BigNum t(b);
    BigNum res = *this-t;
    return res;
}
BigNum BigNum::operator * (const LL& b)const {
    BigNum t(b);
    BigNum res = *this*t;
    return res;
}
BigNum BigNum::operator / (const LL& b)const {
    BigNum res;
    BigNum t1(*this),t2(b),t3(b);
    t1.sign = t2.sign = 1;
    if(t1 < t2) {
        res.assignInt(0);
    }else {
        res.sign = sign*t3.sign;
        LL bb = abs(b);
        int down = 0;
        for(int i = len-1; i >= 0; --i) {
            res.a[i] = (a[i]+down*(MAXN+1))/bb;
            down = a[i]+down*(MAXN+1)-res.a[i]*bb;
        }
        res.len = len;
        while(res.a[res.len-1] == 0 && res.len > 1) {
            res.len--;
        }
    }
    return res;
}
BigNum BigNum::operator ^ (const LL& b)const {
    BigNum res(1);
    if(b != 0) {
        BigNum seed(*this);
        LL bb = b;
        while(bb) {
            if(bb & 1) {
                res = res*seed;
            }
            bb >>= 1;
            seed = seed*seed;
        }
    }
    return res;
}

LL BigNum::operator % (const LL& b)const {
    LL d = 0;
    for(int i = len-1; i >= 0; --i) {
        d = ((d*(MAXN+1))%b+a[i])%b;
    }
    return d;
}

//>= 1
bool BigNum::operator > (const BigNum &t)const {
    if(sign > t.sign || len > t.len) {
        return true;
    }
    if(sign < t.sign || len < t.len) {
        return false;
    }
    bool flag = sign==-1?false:true;
    for(int i = len-1; i >= 0; --i) {
        if(a[i] < t.a[i]) {
            if(flag) return false;
            return true;
        }
        if(a[i] > t.a[i]) {
            if(flag) return true;
            return false;
        }
    }
    return true;
}
//< 1
bool BigNum::operator < (const BigNum &t)const {
    return !(*this > t);
}

int main() {
    char ch[1000];
    LL b,c;
    while(~scanf("%lld%lld",&b,&c)) {
        BigNum bn1(b);
        BigNum bn2(c);
        BigNum bn3 = bn1/c;
        LL d = b/c;
        cout<

좋은 웹페이지 즐겨찾기