Длинная арифметика: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 35: Строка 35:
     }
     }
   
   
     void print() {
     void print() const {
         static char spec[] = "%00d";
         static char spec[] = "%00d";
         spec[2] += BASE_LEN;
         spec[2] += BASE_LEN;
Строка 47: Строка 47:
== Сравнение ==
== Сравнение ==


  int cmp(const BigInteger &that) {
  int cmp(const BigInteger &that) const {
     if (size != that.size)
     if (size != that.size)
         return size < that.size ? -1 : 1;
         return size < that.size ? -1 : 1;
Строка 59: Строка 59:
== Сложение ==
== Сложение ==


  BigInteger add(const BigInteger &that) {
  BigInteger add(const BigInteger &that) const {
     BigInteger res(0LL);         
     BigInteger res(0LL);         
     int carry = 0;
     int carry = 0;
Строка 77: Строка 77:
Предполагается, что уменьшаемое больше вычитаемого.
Предполагается, что уменьшаемое больше вычитаемого.


  BigInteger sub(const BigInteger &that) {
  BigInteger sub(const BigInteger &that) const {
     BigInteger res(0LL);
     BigInteger res(0LL);
     int carry = 0;
     int carry = 0;
Строка 95: Строка 95:
{|
{|
| width="50%"  |
| width="50%"  |
  BigInteger mul(const BigInteger &that) {
  BigInteger mul(const BigInteger &that) const {
     BigInteger res(0LL);         
     BigInteger res(0LL);         
     for (int i = 0; i < size; i++) {
     for (int i = 0; i < size; i++) const {
         int carry = 0;
         int carry = 0;
         for (int j = 0; j < that.size || carry != 0; j++) {
         for (int j = 0; j < that.size || carry != 0; j++) {
Строка 112: Строка 112:
| width="10px" |
| width="10px" |
| width="50%"  |
| width="50%"  |
  BigInteger mul(int that) {
  BigInteger mul(int that) const {
     BigInteger res(0LL);         
     BigInteger res(0LL);         
     int carry = 0;
     int carry = 0;
Строка 133: Строка 133:
{|
{|
| width="50%"  |
| width="50%"  |
BigInteger div(const BigInteger &that) const {
    BigInteger res(0LL), carry(0LL);
    for (int i = size - 1; i >= 0; i--) {
        carry = carry.mul(BigInteger(BASE));
        carry.d[0] = d[i];
        int l = 0, r = BASE - 1, m;
        while (l + 1 < r) {
            m = l + (r - l) / 2;
            if (that.mul(m).cmp(carry) <= 0)
                l = m;
            else
                r = m;
        }
        res.d[i] = that.mul(r).cmp(carry) <= 0 ? r : l;
        carry = carry.sub(that.mul(res.d[i]));
    }   
    res.size = size;
    while (res.size > 1 && res.d[res.size - 1] == 0)
        res.size--;
    return res;
}
| width="10px" |
| width="10px" |
| width="50%"  |
| width="50%"  |
  BigInteger div(int that) {
  BigInteger div(int that) const {
     BigInteger res(0LL);
     BigInteger res(0LL);
     int carry = 0;
     int carry = 0;
Строка 148: Строка 169:
     return res;
     return res;
  }
  }
|}
|}
{|
{|
| width="50%"  |
| width="50%"  |
BigInteger mod(const BigInteger &that) const {
    BigInteger carry(0LL);
    for (int i = size - 1; i >= 0; i--) {
        carry = carry.mul(BigInteger(BASE));
        carry.d[0] = d[i];
        int l = 0, r = BASE - 1, m;
        while (l + 1 < r) {
            m = l + (r - l) / 2;
            if (that.mul(m).cmp(carry) <= 0)
                l = m;
            else
                r = m;
        }
        int digit = that.mul(r).cmp(carry) <= 0 ? r : l;
        carry = carry.sub(that.mul(digit));
    }
    return carry;
}
| width="10px" |
| width="10px" |
| width="50%"  |
| width="50%"  |
  int mod(int that) {
  int mod(int that) const {
     int carry = 0;
     int carry = 0;
     for (int i = size - 1; i >= 0; i--)
     for (int i = size - 1; i >= 0; i--)
Строка 159: Строка 206:
     return carry;
     return carry;
  }
  }
|}
|}



Версия от 21:30, 16 августа 2014

Хранение, ввод и вывод

class BigInteger {

    static const int BASE = 1e9;
    static const int BASE_LEN = 9;
    static const int MAX_SIZE = 1e4;
    int d[MAX_SIZE];
    int size;

public:

    BigInteger(long long val) {
        for (int i = 0; i < MAX_SIZE; i++)
            d[i] = 0;
        size = 0;
        if (val == 0)
            d[size++] = 0;
        while (val > 0) {
            d[size++] = val % BASE;
            val /= BASE;
        }
    }

    BigInteger(char val[]) {
        for (int i = 0; i < MAX_SIZE; i++)
            d[i] = 0;
        size = 0;
        for (int i = strlen(val) - 1; i >= 0; i -= BASE_LEN) {
            int digit = 0;
            for (int j = max(0, i - BASE_LEN + 1); j <= i; j++)
                digit = digit * 10 + val[j] - '0';
            d[size++] = digit;
        }
    }

    void print() const {
        static char spec[] = "%00d";
        spec[2] += BASE_LEN;
        printf("%d", d[size - 1]);
        for (int i = size - 2; i >= 0; i--)
            printf(spec, d[i]);
    }

};

Сравнение

int cmp(const BigInteger &that) const {
    if (size != that.size)
        return size < that.size ? -1 : 1;
    for (int i = size - 1; i >= 0; i--) {
        if (d[i] != that.d[i])
            return d[i] < that.d[i] ? -1 : 1;
    }
    return 0;
}

Сложение

BigInteger add(const BigInteger &that) const {
    BigInteger res(0LL);        
    int carry = 0;
    for (int i = 0; i < max(size, that.size) || carry != 0; i++) {
        long long x = 0LL + d[i] + that.d[i] + carry;
        res.d[i] = x % BASE;
        carry = x / BASE;
    }
    res.size = max(size, that.size) + 1;
    while (res.size > 1 && res.d[res.size - 1] == 0)
        res.size--;
    return res;
}

Вычитание

Предполагается, что уменьшаемое больше вычитаемого.

BigInteger sub(const BigInteger &that) const {
    BigInteger res(0LL);
    int carry = 0;
    for (int i = 0; i < size || carry != 0; i++) {
        long long x = 0LL + d[i] - that.d[i] + carry;
        res.d[i] = (x + BASE) % BASE;
        carry = x < 0 ? -1 : 0;
    }
    res.size = size;
    while (res.size > 1 && res.d[res.size - 1] == 0)
        res.size--;
    return res;
}

Умножение

BigInteger mul(const BigInteger &that) const {
    BigInteger res(0LL);        
    for (int i = 0; i < size; i++) const {
        int carry = 0;
        for (int j = 0; j < that.size || carry != 0; j++) {
            long long x = res.d[i + j] + 1LL * d[i] * that.d[j] + carry;
            res.d[i + j] = x % BASE;
            carry = x / BASE;
        }
    }
    res.size = size + that.size;
    while (res.size > 1 && res.d[res.size - 1] == 0)
        res.size--;
    return res;
}
BigInteger mul(int that) const {
    BigInteger res(0LL);        
    int carry = 0;
    for (int i = 0; i < size || carry != 0; i++) {
        long long x = 1LL * d[i] * that + carry;
        res.d[i] = x % BASE;
        carry = x / BASE;
    }
    res.size = size + 1;
    while (res.size > 1 && res.d[res.size - 1] == 0)
        res.size--;
    return res;
}


Деление и взятие остатка

BigInteger div(const BigInteger &that) const {
    BigInteger res(0LL), carry(0LL);
    for (int i = size - 1; i >= 0; i--) {
        carry = carry.mul(BigInteger(BASE));
        carry.d[0] = d[i];
        int l = 0, r = BASE - 1, m;
        while (l + 1 < r) {
            m = l + (r - l) / 2;
            if (that.mul(m).cmp(carry) <= 0)
                l = m;
            else
                r = m;
        }
        res.d[i] = that.mul(r).cmp(carry) <= 0 ? r : l;
        carry = carry.sub(that.mul(res.d[i]));
    }    
    res.size = size;
    while (res.size > 1 && res.d[res.size - 1] == 0)
        res.size--;
    return res;
}
BigInteger div(int that) const {
    BigInteger res(0LL);
    int carry = 0;
    for (int i = size - 1; i >= 0; i--) {
        long long x = 1LL * carry * BASE + d[i];
        res.d[i] = x / that;
        carry = x % that;
    }
    res.size = size;
    while (res.size > 1 && res.d[res.size - 1] == 0)
        res.size--;
    return res;
}








BigInteger mod(const BigInteger &that) const {
    BigInteger carry(0LL);
    for (int i = size - 1; i >= 0; i--) {
        carry = carry.mul(BigInteger(BASE));
        carry.d[0] = d[i];
        int l = 0, r = BASE - 1, m;
        while (l + 1 < r) {
            m = l + (r - l) / 2;
            if (that.mul(m).cmp(carry) <= 0)
                l = m;
            else
                r = m;
        }
        int digit = that.mul(r).cmp(carry) <= 0 ? r : l;
        carry = carry.sub(that.mul(digit));
    }
    return carry;
}
int mod(int that) const {
    int carry = 0;
    for (int i = size - 1; i >= 0; i--)
        carry = (1LL * carry * BASE + d[i]) % that;
    return carry;
}












Ссылки на задачи

Ссылки