Изменения

Алгоритмы Приведённые ниже алгоритмы корректны в силу того, что они являются реализацией "школьных" алгоритмов действий в столбик.: <tex>A = abc = 100 \cdot a + 10 \cdot b + c </tex> <tex>B = de = 10 \cdot d + e </tex> Тогда сумма <tex>A + B = abc + de = (100 \cdot a + 10 \cdot b + c) + (10 \cdot d + e) = 100 \cdot a + 10 \cdot (b + d) + (c + e) </tex> Разность <tex>A - B = abc - de = (100 \cdot a + 10 \cdot b + c) - (10 \cdot d + e) = 100 \cdot a + 10 \cdot (b - d) + (c - e) </tex> Произведение <tex>A \cdot B = abc \cdot de = (100 \cdot a + 10 \cdot b + c) \cdot (10 \cdot d + e) = 100 \cdot a \cdot 10 \cdot d + 10 \cdot b \cdot 10 \cdot d + c \cdot 10 \cdot d + 100 \cdot a \cdot e + 10 \cdot b \cdot e + c \cdot e = 1000 \cdot a \cdot d + 100 \cdot (a \cdot e + b \cdot d) + 10 \cdot (b \cdot e + c \cdot d) + c \cdot e</tex>

Алгоритм не требует <tex>O(n + m)</tex> дополнительной памяти, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>.

'''function''' getSum(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>''' carry = 0 i = 0 '''while''' i < max(a.size(),b.size()) || carry '''if''' i == a.size() a.push_back(0) '''if''' i < b.size() a[i] += carry + (b[i < b.size() ? b] '''else''' a[i] : 0)+= carry carry = a[i] <tex>\geqslant</tex> base '''if''' carry a[i] -= base i++ '''return''' a

Алгоритм не требует <tex>Oдополнительной памяти. '''function''' getSub(n + m)a: '''vector</texint> памяти''', где b: '''vector<texint>n, m'''): '''vector</texint> — длины чисел <tex>a</tex> и <tex>b</tex>.''' carry = 0 i = 0 '''while''' i < b.size() || carry '''if''' i < b.size() a[i] -= carry + (b[i < b.size() ? b] '''else''' a[i] : 0)-= carry carry = a[i] < 0 '''if''' carry a[i] += base i++ '''while''' a.size() > 1 && a.back() == 0 a.pop_back() <font color=green>//Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font> '''return''' a

Алгоритм требует <tex>O(n \cdot m)</tex> памяти, где <tex>n, m</tex> — длины чисел <tex>a</tex> и <tex>b</tex>длина длинного числа.

'''function''' getCompLongShort(a: '''vector<int>''', b: '''int'''): '''vector<int>''' carry = 0 i = 0 '''while''' i < a.size() || carry '''if''' i == a.size() a.push_back(0) cur = carry + a[i] <tex>\cdot</tex> 1ll <tex>\cdot</tex> b; a[i] = cur '''mod''' base carry = cur / base i++ '''whilereturn''' a.size() > 1 && a.back() == 0 a.pop_back() <font color=green>//Здесь мы после выполнения деления удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.</font>

'''function''' getCompLongLong(a: '''vector<int>''', b: '''vector<int>'''): '''vector<int>''' carry = 0 i = 0 '''while''' i < a.size() j = 0 '''while''' (j < b.size() || carry) '''if''' j < b.size() cur = c[i + j] + a[i] <tex>\cdot</tex> 1ll <tex>\cdot</tex> (b[j < (int)b.size() ? b] + carry '''else''' cur = c[i + j] : 0) + carry c[i + j] = cur '''mod''' base carry = cur / base i j++ j i++ '''while''' c.size() > 1 && c.back() == 0 c.pop_back() '''return''' c

Алгоритм не требует <tex>Oдополнительной памяти. '''function''' getDivLongShort(n + m)</tex> памяти, где a: '''vector<texint>n''', m</tex> — длины чисел <tex>a</tex> и <tex>b: '''int'''): '''vector</texint>.'''  carry = 0 i = a.size() - 1 '''while''' i <tex>\geqslant</tex> 0 cur = a[i] + carry <tex>\cdot</tex> 1ll <tex>\cdot</tex> base a[i] = cur '''mod''' base carry = cur / base i-- '''while''' a.size() > 1 && a.back() == 0 a.pop_back() '''return''' a