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

Того что тут написано вроде больше нигде нет на русском. Скорее всего это нифига не понятно, но раз уж у меня был конспект по этому, то я залью его сюда.

Нам понадобится Быстрое преобразование Фурье чтобы иметь умножение за $O(n \log n)$.

Быстрое деление двух чисел

У нас будут 2 функции, рекурсивно вызывающие друг друга. $n$ всегда будет являться точной степенью двух, $|a|$ будет обозначать длину числа a.

div21 — делит число $a$ длиной не более $2n$ на число $b$ длиной не более $n$, при условии, что ответ по длине не превосходит $n$.
div32 — делит число $a$ длиной не более $3n$ на число $b$ длиной не более $2n$, при условии, что ответ по длине не превосходит $n$.

Обе функции должны возвращать результат деления и остаток.

div21

Как работает div21: пусть $m=\frac{n}{2}$. Тогда $a$ имеет длину не более $4m$, на $b$ имеет длину не более $2m$, а ответ по длине не превосходит $2m$. Возьмём первые $|a| - m \le 3m$ цифр числа $a$ и разделим на число $b$ при помощи div32. Ответ по длине не превзойдёт $m$, так как иначе $a/b$ было бы больше по длине чем $2m$. Далее возьмём остаток после этого деления, домножим его на $10^m$, и припишем к нему последние $m$ цифр числа $a$. После этого разделим это число на $b$. Так как $|b| \le 2m$, то длина остатка не превосходит $2m$, значит длина остатка, домноженного на $10^m$ на превосходит $m$, тогда для деления мы можем использовать функцию div32. Далее умножим результат первого деления на $m$ и прибавил результат второго деления. Так мы получим ответ.

div32

Как работает div32: пусть $|b| \le n$. Тогда так как длина ответа не превосходит $n$, $|a| \le 2n$, тогда будем использовать $div21$. Иначе возьмём $b_1$, образованное первыми $n$ цифрами из $b$. Возьмём $a_1$, образованное первыми $|a| - (|b| - n)$ цифрами из $a$. (Т.е. обрежем $a$ и $b$ на одинаковое число цифр в конце так, чтобы длина $b$ стала равна $n$) Обозначим за $k = |b| - n$. (т.е. сколько цифр в конце мы отрезали от $a$ и от $b$). Обозначим за $r_a = a - a_1 \cdot 10^k$, $r_b = b - b_1 \cdot 10^k$. (т.е. обозначим за $r_a$ и $r_b$ то, что мы отрезали от $a$ и от $b$). Тогда $a / b = (a_1 \cdot 10^k + r_a) / (b_1 \cdot 10^k + r_b)$.

Утверждение:
${a_1} / {b_1} \ge {a}/{b}$

Доказательство:
Это верно так как $a_1 / b_1 = (a_1 \cdot 10^k) / (b_1 \cdot 10^k)$. Так как $k < n$, и $b_1 \le 10^n$, то для любого $x < 10^k$ $(a_1 \cdot 10^k + x) / (b_1 \cdot 10^k) = (a_1 \cdot 10^k) / (b_1 \cdot 10^k)$. Ну и тогда понятно, что $(a_1 \cdot 10^k + x) / (b_1 \cdot 10^k) \ge (a_1 \cdot 10^k + x) / b$ так как $b \ge b_1 \cdot 10^k$. Тогда если $x=r_a$, то мы всё доказали.

Сразу за этим утверждением следует следующее утверждение.

Утверждение:
${a_1} / ({b_1} + 1) \le {a}/{b}$

Доказательство:
Замечаем, что $b < (b_1 + 1) \cdot 10^k$. Тогда $\frac{a}{b} \ge \frac{a}{(b_1 + 1) \cdot 10^k}$. Дальше как и в прошлом утверждении так как у знаменателя $((b_1 + 1) \cdot 10^k)$ в конце $k$ нулей, то если от числителя отбросить последние $k$ цифр, результат не поменяется. Тогда получим, что $\frac{a}{(b_1 + 1) \cdot 10^k} = \frac{a_1}{b_1 + 1}$. Тогда ${a_1} / ({b_1} + 1) \le {a}/{b}$.

Тогда $a_1 / b_1 \ge a / b \ge a_1 / (b_1 + 1)$. Теперь возьмём $q = a_1 / b_1$ и будем пытаться получить из него $a / b$. Несложно заметить, что на самом деле $q \ge a / b \ge q - 10$. Для этого надо показать, что:

Утверждение:
$q - 10 \le a_1 / (b_1 + 1)$

Доказательство:
Домножим на $(b_1 + 1)$. $(q - 10) \cdot (b_1 + 1) = (a_1 / b_1 - 10) \cdot (b_1 + 1) = a_1 - 10 \cdot b_1 + q - 10$. Т.к. $q = a_1 / b_1$ по длине не превышает $n$, а $b$ по длине ровно равно $n$, то $10b > q$. Тогда в предыдущем выражении мы можем убрать $-10\cdot b_1 + q$ и от этого оно только возрастёт. Но тогда у нас останется $a_1 - 10$. Нетрудно понять, что это меньше $a_1$, а значит при домножении обеих частей искомого неравенства мы получили корректное неравенство. Тогда $q - 10 < a_1 / (b_1 + 1)$.

Тогда $a_1 / b_1 \ge a / b \ge a_1 / b_1 - 10$. Тогда для div32 получается следующий алгоритм. Строим числа $a_1$ и $b_1$. С помощью div21 разделим $a_1$ на $b_1$. (Если $a_1 > b_1 \cdot 10^n$, будем считать что результат равен $10^n - 1$). Далее вычтем из $a$ результат деления, домноженный на $b$ и посчитаем остаток от текущего деления. Пока остаток меньше нуля, будем прибавлять к нему $b$ и вычитать из частного 1. Таких действий мы сделаем не более $n$.

При совсем маленьких числах надо делить уже используя int-овое деление.

Можно увеличить базу с 10 до $10^9$, но делать это надо аккуратно.

Асимптотику доказать несложно. $div21(n)$ делает $O(n)$ действий и вызывает div32 два раза. $div32(n)$ делает $O(n \log n)$ действий (т.к. там есть операция умножения) и возможно вызывает $div21(n)$. Таким образом $div21(n)$ делает $O(n \log n)$ действий и два раза вызывает div21. Таким образом время работы $O(n \log^2 n)$.

Более подробное описание и доказательство этого алгоритма можно найти по ссылке

Автор конспекта: Филипп Грибов

По всем вопросам пишите в telegram @grphil