🧮 Реализация на Дълги Числа (BigInt)

В C++ най-големият целочислен тип unsigned long long поддържа числа до \(\approx 1.8 \times 10^{19}\). Много задачи обаче изискват работа с числа със стотици или хиляди цифри. За разлика от Python и Java, C++ няма вградена поддръжка за BigInteger, така че трябва да си я напишем сами.

1. Стратегия за съхранение

Най-ефективният начин е да съхраняваме числото в std::vector<int>, но не цифра по цифра (база 10), а групирайки ги, например по 9 цифри (база \(10^9\)). * База \(10^9\) се побира в int. * Умножението на две "цифри" (до \(10^{18}\)) се побира в long long. * Намалява броя на операциите 9 пъти спрямо база 10.

Векторът пази цифрите в обратен ред (най-младшите са на индекс 0), за да може лесно да се разширява.

2. Пълна имплементация (Template)

Ето една компактна, но функционална структура, която можете да използвате в състезания:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

const int BASE = 1e9;

struct BigInt {
    vector<int> digits;

    // Конструктори
    BigInt() {}
    BigInt(long long v) {
        if (v == 0) digits.push_back(0);
        while (v > 0) {
            digits.push_back(v % BASE);
            v /= BASE;
        }
    }
    BigInt(string s) {
        for (int i = (int)s.length(); i > 0; i -= 9) {
            if (i < 9) digits.push_back(stoi(s.substr(0, i)));
            else digits.push_back(stoi(s.substr(i - 9, 9)));
        }
        trim();
    }

    void trim() {
        while (digits.size() > 1 && digits.back() == 0) 
            digits.pop_back();
    }

    // Оператори за сравнение
    bool operator<(const BigInt &other) const {
        if (digits.size() != other.digits.size()) 
            return digits.size() < other.digits.size();
        for (int i = digits.size() - 1; i >= 0; i--)
            if (digits[i] != other.digits[i]) 
                return digits[i] < other.digits[i];
        return false;
    }

    bool operator>(const BigInt &other) const { return other < *this; }
    bool operator==(const BigInt &other) const { return !(*this < other) && !(other < *this); }

    // Събиране
    BigInt operator+(const BigInt &other) const {
        BigInt res = *this;
        int carry = 0;
        for (size_t i = 0; i < max(res.digits.size(), other.digits.size()) || carry; ++i) {
            if (i == res.digits.size()) res.digits.push_back(0);
            long long current = res.digits[i] + carry + (i < other.digits.size() ? other.digits[i] : 0);
            res.digits[i] = current % BASE;
            carry = current / BASE;
        }
        return res;
    }

    // Умножение с късо число (int)
    BigInt operator*(int v) const {
        if (v == 0) return BigInt(0);
        BigInt res = *this;
        long long carry = 0;
        for (size_t i = 0; i < res.digits.size() || carry; ++i) {
            if (i == res.digits.size()) res.digits.push_back(0);
            long long cur = carry + (long long)res.digits[i] * v;
            res.digits[i] = cur % BASE;
            carry = cur / BASE;
        }
        res.trim();
        return res;
    }

    // Умножение с BigInt (School method O(N*M))
    BigInt operator*(const BigInt &other) const {
        BigInt res;
        res.digits.resize(digits.size() + other.digits.size(), 0);
        for (size_t i = 0; i < digits.size(); ++i) {
            long long carry = 0;
            for (size_t j = 0; j < other.digits.size() || carry; ++j) {
                long long cur = res.digits[i+j] + (long long)digits[i] * (j < other.digits.size() ? other.digits[j] : 0) + carry;
                res.digits[i+j] = cur % BASE;
                carry = cur / BASE;
            }
        }
        res.trim();
        return res;
    }

    // Изход
    friend ostream& operator<<(ostream &os, const BigInt &bi) {
        if (bi.digits.empty()) { os << 0; return os; }
        os << bi.digits.back();
        for (int i = bi.digits.size() - 2; i >= 0; i--) {
            os << setfill('0') << setw(9) << bi.digits[i];
        }
        return os;
    }
};

3. Python или Java?

Ако задачата позволява използването на други езици и ограничението за време не е твърде строго (Python е по-бавен), често е по-лесно просто да превключите езика. В Python int автоматично поддържа произволна точност.

Python пример:

a = int(input())
b = int(input())
print(a * b)

4. Оптимизации

1. Карацуба (Karatsuba): За много големи числа (напр. над 2000-3000 цифри) стандартното умножение \(O(N^2)\) е бавно. Алгоритъмът на Карацуба работи за \(O(N^{\log_2 3}) \approx O(N^{1.58})\).
2. FFT (Fast Fourier Transform): За екстремно големи числа (\(10^5\) цифри), умножението става за \(O(N \log N)\) (виж Тема 44).

5. Задачи

1. UVa 10106 - Product: Просто умножение на две големи числа.
2. SPOJ JULKA: Събиране и изваждане / деление на 2.
3. Codeforces 1042D: Може да се наложи BigInt за междинни сметки.

---

6. Деление на дълги числа

Делението е най-сложната операция при BigInt. Има два основни подхода:

6.1. Двоично търсене

Ако делим \(A\) на \(B\) и искаме частното \(Q\), можем да използваме двоично търсене върху отговора: * Търсим най-голямото \(Q\), за което \(Q \times B \le A\). * Остатъкът е \(R = A - Q \times B\).

Сложност: \(O((\log A) \cdot M)\), където \(M\) е сложността на умножението.

6.2. "School Division" метод

Подобно на дългото деление, което учим на училище, можем да делим "цифра" по "цифра" (в нашата база \(10^9\)):

BigInt divide(const BigInt& dividend, int divisor, int& remainder) {
    BigInt result;
    long long carry = 0;

    for (int i = dividend.digits.size() - 1; i >= 0; i--) {
        long long current = carry * BASE + dividend.digits[i];
        result.digits.push_back(current / divisor);
        carry = current % divisor;
    }

    remainder = carry;
    reverse(result.digits.begin(), result.digits.end());
    result.trim();
    return result;
}

---

7. Факториел на големи числа

Класическа задача: Изчислете \(N!\) за \(N \le 1000\).

BigInt factorial(int n) {
    BigInt result(1);
    for (int i = 2; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Например, \(100!\) има 158 цифри и е извън обхвата на всички вградени типове.

---

8. GCD на дълги числа

Алгоритъмът на Евклид работи и за BigInt, но ако едното число е малко (int), има по-бърз метод:

int gcd_bigint_int(BigInt a, int b) {
    // Евклид с mod операция
    while (b != 0) {
        int remainder;
        a = divide(a, b, remainder);
        swap(a, BigInt(b));
        b = remainder;
    }
    return a.digits[0]; // Резултатът ще е малко число
}

---

9. Степенуване на BigInt

За \(A^B \pmod{M}\), ако \(A\) е BigInt, а \(B\) и \(M\) са обикновени числа:

BigInt powerMod(BigInt base, int exp, int mod) {
    BigInt result(1);
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base); // После вземете модул
        }
        base = (base * base); // После вземете модул
        exp /= 2;
    }
    return result;
}

Забележка: За огромни модули може да е необходимо mod да е BigInt.

---

10. Алтернативи и оптимизации

10.1. Използване на Python

Ако състезанието позволява:

a = int(input())
b = int(input())
print(a ** b)  # Python автоматично работи с произволно големи числа

10.2. Библиотеки в C++

• GMP (GNU Multiple Precision Library): Изключително бърза и оптимизирана библиотека за произволно големи числа.
• Обаче, повечето състезания НЕ позволяват външни библиотеки.

---

🏁 Заключение

Имплементацията на BigInt е важно умение за състезатели. Добре е да имате подготвен шаблон, който да копирате при нужда. Ключовите елементи са: * Избор на подходяща база (\(10^9\) е оптимална). * Коректно управление на carry при аритметични операции. * trim() за премахване на водещи нули. * Тестване с екстремни случаи (0, много големи числа, еднакви числа).

Въпреки че изглежда сложно, след като го напишете веднъж, можете да го използвате многократно!