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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
 
Строка 224: Строка 224:
  struct BigInteger {
  struct BigInteger {
     vector<int> digits;
     vector<int> digits;
    inline static const int BASE = 1e9;
    inline static const int DIGIT_WIDTH = 9;
    inline int digit(int index) const {
        return index < digits.size() ? digits[index] : 0;
    }
    inline int &digit(int index) {
        if (digits.size() <= index)
            digits.resize(index + 1);
        return digits[index];
    }
    inline void removeZeros() {
        while (!digits.empty() && !digits.back())
            digits.pop_back();
    }
   
   
     BigInteger(long long value = 0) {
     BigInteger(long long value = 0) {
         for ( ; value; value /= 10)
         for (; value; value /= BASE)
             digits.push_back(value % 10);
             digits.push_back(value % BASE);
    }
    BigInteger(const string &s) {
        for (int r = s.size() - 1; r >= 0; r -= DIGIT_WIDTH) {
            int l = max(r - DIGIT_WIDTH + 1, 0);
            digits.push_back(stoi(s.substr(l, r - l + 1)));
        }
        removeZeros();
     }
     }
   
   
Строка 233: Строка 258:
         BigInteger res;
         BigInteger res;
         for (int i = 0, carry = 0; i < digits.size() || i < that.digits.size() || carry; i++) {
         for (int i = 0, carry = 0; i < digits.size() || i < that.digits.size() || carry; i++) {
             int digit = i < digits.size() ? digits[i] : 0;
             int cur = digit(i) + that.digit(i) + carry;
            int thatDigit = i < that.digits.size() ? that.digits[i] : 0;
             res.digits.push_back(cur % BASE);
            int sum = digit + thatDigit + carry;
             carry = cur / BASE;
             res.digits.push_back(sum % 10);
             carry = sum / 10;
         }
         }
         return res;
         return res;
    }
    BigInteger operator * (const BigInteger &that) const {
        BigInteger res;
        for (int i = 0, carry = 0; i < digits.size(); i++) {
            for (int j = 0; j < that.digits.size() || carry; j++) {
                long long cur = res.digit(i + j) + 1LL * digit(i) * that.digit(j) + carry;
                res.digit(i + j) = cur % BASE;
                carry = cur / BASE;
            }
        }
        res.removeZeros();
        return res;
    }
    BigInteger operator / (int that) const {
        BigInteger res;
        for (int i = digits.size() - 1, carry = 0; i >= 0; i--) {
            long long cur = 1LL * carry * BASE + digit(i);
            res.digit(i) = cur / that;
            carry = cur % that;
        }
        res.removeZeros();
        return res;
    }
    friend istream &operator >> (istream &in, BigInteger &value) {
        string s;
        in >> s;
        value = BigInteger(s);
        return in;
     }
     }
   
   
Строка 246: Строка 300:
             out << 0;
             out << 0;
         } else {
         } else {
             for (int i = value.digits.size() - 1; i >= 0; i--)
            out << value.digits.back();
             for (int i = (int)value.digits.size() - 2; i >= 0; i--) {
                out.width(DIGIT_WIDTH);
                out.fill('0');
                 out << value.digits[i];
                 out << value.digits[i];
            }
         }
         }
         return out;
         return out;

Текущая версия от 23:40, 13 августа 2024

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

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 = 0) {
        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 + '0';
        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;
} 
bool operator < (const BigInteger &that) const {
    return cmp(that) < 0;
}
bool operator == (const BigInteger &that) const {
    return cmp(that) == 0;
}

Сложение

BigInteger operator + (const BigInteger &that) const {
    BigInteger res;        
    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 operator - (const BigInteger &that) const {
    BigInteger res;
    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 operator * (const BigInteger &that) const {
    BigInteger res;        
    for (int i = 0; i < size; i++) {
        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 operator * (int that) const {
    BigInteger res;        
    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 operator / (const BigInteger &that) const {
    BigInteger res, carry;
    for (int i = size - 1; i >= 0; i--) {
        carry = carry * BASE;
        carry.d[0] = d[i];
        int l = 0, r = BASE - 1, m;
        while (l + 1 < r) {
            m = l + (r - l) / 2;
            if ((that * m).cmp(carry) <= 0)
                l = m;
            else
                r = m;
        }
        res.d[i] = (that * r).cmp(carry) <= 0 ? r : l;
        carry = carry - that * res.d[i];
    }    
    res.size = size;
    while (res.size > 1 && res.d[res.size - 1] == 0)
        res.size--;
    return res;
}

BigInteger operator / (int that) const {
    BigInteger res;
    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 operator % (const BigInteger &that) const {
    BigInteger carry;
    for (int i = size - 1; i >= 0; i--) {
        carry = carry * BASE;
        carry.d[0] = d[i];
        int l = 0, r = BASE - 1, m;
        while (l + 1 < r) {
            m = l + (r - l) / 2;
            if ((that * m).cmp(carry) <= 0)
                l = m;
            else
                r = m;
        }
        int digit = (that * r).cmp(carry) <= 0 ? r : l;
        carry = carry - that * digit;
    }
    return carry;
}

int operator % (int that) const {
    int carry = 0;
    for (int i = size - 1; i >= 0; i--)
        carry = (1LL * carry * BASE + d[i]) % that;
    return carry;
}

Длинная арифметика на vector

struct BigInteger {
    vector<int> digits;
    inline static const int BASE = 1e9;
    inline static const int DIGIT_WIDTH = 9;

    inline int digit(int index) const {
        return index < digits.size() ? digits[index] : 0;
    }

    inline int &digit(int index) {
        if (digits.size() <= index)
            digits.resize(index + 1);
        return digits[index];
    }

    inline void removeZeros() {
        while (!digits.empty() && !digits.back())
            digits.pop_back();
    }

    BigInteger(long long value = 0) {
        for (; value; value /= BASE)
            digits.push_back(value % BASE);
    }

    BigInteger(const string &s) {
        for (int r = s.size() - 1; r >= 0; r -= DIGIT_WIDTH) {
            int l = max(r - DIGIT_WIDTH + 1, 0);
            digits.push_back(stoi(s.substr(l, r - l + 1)));
        }
        removeZeros();
    }

    BigInteger operator + (const BigInteger &that) const {
        BigInteger res;
        for (int i = 0, carry = 0; i < digits.size() || i < that.digits.size() || carry; i++) {
            int cur = digit(i) + that.digit(i) + carry;
            res.digits.push_back(cur % BASE);
            carry = cur / BASE;
        }
        return res;
    }

    BigInteger operator * (const BigInteger &that) const {
        BigInteger res;
        for (int i = 0, carry = 0; i < digits.size(); i++) {
            for (int j = 0; j < that.digits.size() || carry; j++) {
                long long cur = res.digit(i + j) + 1LL * digit(i) * that.digit(j) + carry;
                res.digit(i + j) = cur % BASE;
                carry = cur / BASE;
            }
        }
        res.removeZeros();
        return res;
    }

    BigInteger operator / (int that) const {
        BigInteger res;
        for (int i = digits.size() - 1, carry = 0; i >= 0; i--) {
            long long cur = 1LL * carry * BASE + digit(i);
            res.digit(i) = cur / that;
            carry = cur % that;
        }
        res.removeZeros();
        return res;
    }

    friend istream &operator >> (istream &in, BigInteger &value) {
        string s;
        in >> s;
        value = BigInteger(s);
        return in;
    }

    friend ostream &operator << (ostream &out, const BigInteger &value) {
        if (value.digits.empty()) {
            out << 0;
        } else {
            out << value.digits.back();
            for (int i = (int)value.digits.size() - 2; i >= 0; i--) {
                out.width(DIGIT_WIDTH);
                out.fill('0');
                out << value.digits[i];
            }
        }
        return out;
    }
};

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

Ссылки

Источник — https://acm.khpnets.info/w39/index.php?title=Длинная_арифметика&oldid=2917