Деление больших чисел алгоритм

Однозначные натуральные числа легко делить в уме. Но как делить многозначные числа? Если в числе уже более двух разрядов, устный счет может занять много времени, да и вероятность ошибки при операциях с многоразрядными числами возростает.

Деление столбиком – удобный метод, часто применяемый для операции деления многозначных натуральных чисел. Именно этому методу и посвящена данная статья. Ниже мы рассмотрим, как выполнять деление столбиком. Сначала рассмотрим агоритм деления в столбик многозначного числа на однозначное, а затем – многозначного на многозначное. Помимо теории в статье приведены практические примеры деления в столбик.

Запись чисел при делении столбиком

Удобнее всего вести записи на бумаге в клетку, так как при расчетах разлиновка не даст вам запутаться в разрядах. Сначала делимое и делитель записываются слева направо в одну строчку, а затем разделяются специальным знаком деления в столбик, который имеет вид:

Пусть нам нужно разделить 6105 на 55 , запишем:

Промежуточные вычисление будем записывать под делимым, а результат запишется под делителем. В общем случае схема деления столбиком выглядит так:

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

Например, для деления чисел 614 808 и 51 234 понадобится меньше места, чем для деления числа 8 058 на 4. Несмотря на то, что во втором случае числа меньше, разница в числе их разрядов больше, и вычисления будут более громоздкими. Проиллюстрируем это:

Деление столбиком на однозначное число

Практические навыки удобнее всего отрабатывать на простых примерах. Поэтому, разделим числа 8 и 2 в столбик. Конечно, данную операцию легко произвести в уме или по таблице умножения, однако провести подробный разбор будет полезно для наглядности, хоть мы и так знаем, что 8 ÷ 2 = 4 .

Итак, сначала запишем делимое и делитель согласно методу деления в столбик.

Следующим шагом нужно выяснить, сколько делителей содержит делимое. Как это сделать? Последовательно умножаем делитель на 0 , 1 , 2 , 3 . . Делаем это до тех пор, пока в результате не получится число, равное или большее, чем делимое. Если в результате сразу получается число, равное делимому, то под делителем записываем то число, на которое умножали делитель.

Иначе, когда получается число, большее чем делимое, под делителем записываем число, вычисленное на предпоследнем шаге.На место неполного частного записываем то число, на которое умножался делитель на предпоследнем шаге.

Вернемся к примеру.

2 · 0 = 0 ; 2 · 1 = 2 ; 2 · 2 = 4 ; 2 · 3 = 6 ; 2 · 4 = 8

Итак, мы сразу получили число, равное делимому. Записываем его под делимым, а число 4 , на которое мы умножали делитель, записываем на место частного.

Теперь осталось вычесть числа под делителем (также по методу столбика). В нашем случае 8 – 8 = 0 .

Данный пример – деление чисел без остатка. Число, получащееся после вычитания – это остаток деления. Если оно равно нулю, значит числа разделились без остатка.

Теперь рассмотрим пример, когда числа делятся с остатком. Разделим натуральное число 7 на натуральное число 3 .

В данном случае, последовательно умножая тройку на 0 , 1 , 2 , 3 . . получаем в результате:

3 · 0 = 0 7 ; 3 · 1 = 3 7 ; 3 · 2 = 6 7 ; 3 · 3 = 9 > 7

Под делимым записываем число , полученное на предпоследнем шаге. По делителем записываем число 2 – неполное частное, полученное на предпоследнем шаге. Именно на двойку мы умножали делитель, когда получили 6 .

В завершение операции вычитаем 6 из 7 и получаем:

Данный пример – деление чисел с остатком. Неполное частное равно 2 , а остаток равен 1 .

Теперь, после рассмотрения элементарых примеров, перейдем к делению многозначных натуральных чисел на однозначные.

Алгоритм деления столбиком будем рассматривать на примере деления многозначного числа 140288 на число 4 . Сразу скажем, что понять суть метода гораздо легче на практических примерах, и данный пример выбран не случайно, так как иллюстрирует все возможные нюансы деления натуральных чисел столбиком.

Алгоритм деления столбиком

1. Запишем числа вместе с символом деления столбиком. Теперь смотрим на первую слева цифру в записи делимого. Возможны два случая: число, определяемое этой цифрой, больше, чем делитель, и наоборот. В первом случае мы работаем с этим числом, во втором – дополнительно берем следующую цифру в записи делимого и работаем с соответствующим двузначным числом. Согласно с этим пунктом, выделим в записе примера число, с которым будем работать первоначально. Это число – 14 , так как первая цифра делимого 1 меньше, чем делитель 4 .

2. Определяем, сколько раз числитель содержится полученном числе. Обозначим это число как x = 14 . Последовательно умножаем делитель 4 на каждый член ряда натуральных чисел ℕ , включая нуль : 0 , 1 , 2 , 3 и так далее. Делаем это, пока не получим в результате x или число, большее чем x . Когда в результате умножения получается число 14 , записываем его под выделенным числом по правилам записи вычитания в столбик. Множитель, на который умножался делитель, записываем под делітелем. Если в результате умножения получается число, большее чем x , то под выделенным числом записываем число, полученное на предпоследнем шаге, а на место неполного частного (под делителем) пишем множитель, на который на предпоследнем шаге проводилось умножение.

В соответствии с алгоритмом имеем:

4 · 0 = 0 14 ; 4 · 1 = 4 14 ; 4 · 2 = 8 14 ; 4 · 3 = 12 14 ; 4 · 4 = 16 > 14 .

Под выделенным числом записываем число 12 , полученное на предпоследнем шаге. На место частного записываем множитель 3 .

3. Столбиком вычитаем из 14 12 , результат записываем под горизонтальной чертой. По аналогии с первым пунктом сравниваем полученное число с делителем.

4. Число 2 меньше числа 4 , поэтому записываем под горизонтальной чертой после двойки цифру,расположенную в следующем разряде делимого. Если же в делимом более нет цифр, то на этом операция деления заканчивается. В нашем примере после полученного в предыдущем пункте числа 2 записываем следубщую цифру делимого – 0 . В итоге отмечаем новое рабочее число – 20 .

Пункты 2 – 4 повторяются циклически до окончания операции деления натуральных чисел столбиком.

2. Снова посчитаем, сколько делителей содержится в числе 20 . Умножая 4 на 0 , 1 , 2 , 3 . . получаем:

Так как мы получили в результе число, равное 20 , записываем его под отмеченным числом, а на месте частного, в следубщем разряде, записываем 5 – множитель, на который проводилось умножение.

3. Проводим вычитание столбиком. Так как числа равны, получаем в результате число ноль: 20 – 20 = 0 .

4. Мы не будем записывать число ноль, так как данный этап – еще не окончание деления. Просто запомним место, куда мы могли его записать и запишем рядом число из следующего разряда делимого. В нашем случае – число 2 .

Принимаем это число за рабочее и снова выполняем пункты алгоритма.

2. Умножаем делитель на 0 , 1 , 2 , 3 . . и сравниваем результат с отмеченным числом.

4 · 0 = 0 2 ; 4 · 1 = 4 > 2

Соответственно, под отмеченным числом записываем число 0 , и под делителем в следующий разряд частного также записываем 0 .

3. Выполняем операцию вычитания и под чертой записываем результат.

4. Справа под чертой добавляем цифру 8 , так как это следующая цифра делимого числа.

Таким образом, получаем новое работчее число – 28 . Снова повторяем пункты алгоритма.

Проделав все по правилам, получаем результат:

Переносим под черту вниз последнюю цифру делимого – 8 . В последний раз повторяем пункты алгоритма 2 – 4 и получаем:

В самой нижней строчке записываем число 0 . Это число записывается только на последнем этапе деления, когда операция завершена.

Таким образом, результатом деления числа 140228 на 4 является число 35072 . Данный пример разобран очень подробно, и при решении практических заданий расписывать все действия столь досканально не нужно.

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

Пример 1. Деление натуральных чисел в столбик

Разделим натуральное число 7136 на натуральное число 9 .

После второго, третьего и четвертого шага алгоритма запись примет вид:

Последний проход, и поучаем результат:

Ответ: Неполное неполное частное чисел 7136 и 9 равно 792 , а остаток равен 8 .

При решении практических примеров в иделе вообще не использовать пояснения в виде словесных комментариев.

Пример 2. Деление натуральных чисел в столбик

Разделим число 7042035 на 7 .

Деление многозначных натуральных чисел столбиком

Алгоритм деления многозначных чисел в столбик очень похож на рассмотренный ранее алгорим деления многозначного числа на однозначное. Если быть точнее, изменения касаются только первого пункта, а пункты 2 – 4 остаются неизменными.
Если при делении на однозначное число мы смотрели только на первую цифру делимого, то теперь будем смотреть на столько цифр, сколько есть в делителе.Когда число, определяемое этими цифрами, больше делителя, принимам его за рабочее число. Иначе – добавляем еще одну цифру из следующего разряда делимого. Затем следуем пунктам описанного выше алгоритма.

Рассмотрим применение алгоритма деления многозначных чисел на примере.

Пример 3. Деление натуральных чисел в столбик

Разделим 5562 на 206 .

В записи делителя участвуют три знака, поэтому в делимом сразу выделим число 556 .
556 > 206 , поэтому принимаем это число за рабочее и переходим к пункту 2 аглоритма.
Умножаем 206 на 0 , 1 , 2 , 3 . . и получаем:

206 · 0 = 0 556 ; 206 · 1 = 206 556 ; 206 · 2 = 412 556 ; 206 · 3 = 618 > 556

618 > 556 , поэтому под делителем записываем результат предпоследнего действия, а под делимым – множитель 2

Выполняем вычитание столбиком

В результате вычитания имеем число 144 . Справа от результата под чертой записываем число из соответствующего разряда делимого и получаем новое рабочее число – 1442 .

Повторяем с ним пункты 2 – 4 . Получаем:

206 · 5 = 1030 1442 ; 206 · 6 = 1236 1442 ; 206 · 7 = 1442

Под отмеченным рабочим числом записываем 1442 , а в следующий разряд частного записываем цифру 7 – множитель.

Выполняем вычитание в столбик, и понимаем, что на этом операция деления окончена: в делителе более нет цифр, чтобы записать их правее от результата вычитания.

В завершение данной темы приведем еще один пример деления многозначных чисел в столбик, уже без пояснений.

Пример 5. Деление натуральных чисел в столбик

Однозначные натуральные числа легко делить в уме. Но как делить многозначные числа? Если в числе уже более двух разрядов, устный счет может занять много времени, да и вероятность ошибки при операциях с многоразрядными числами возростает.

Деление столбиком – удобный метод, часто применяемый для операции деления многозначных натуральных чисел. Именно этому методу и посвящена данная статья. Ниже мы рассмотрим, как выполнять деление столбиком. Сначала рассмотрим агоритм деления в столбик многозначного числа на однозначное, а затем – многозначного на многозначное. Помимо теории в статье приведены практические примеры деления в столбик.

Запись чисел при делении столбиком

Удобнее всего вести записи на бумаге в клетку, так как при расчетах разлиновка не даст вам запутаться в разрядах. Сначала делимое и делитель записываются слева направо в одну строчку, а затем разделяются специальным знаком деления в столбик, который имеет вид:

Пусть нам нужно разделить 6105 на 55 , запишем:

Промежуточные вычисление будем записывать под делимым, а результат запишется под делителем. В общем случае схема деления столбиком выглядит так:

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

Например, для деления чисел 614 808 и 51 234 понадобится меньше места, чем для деления числа 8 058 на 4. Несмотря на то, что во втором случае числа меньше, разница в числе их разрядов больше, и вычисления будут более громоздкими. Проиллюстрируем это:

Деление столбиком на однозначное число

Практические навыки удобнее всего отрабатывать на простых примерах. Поэтому, разделим числа 8 и 2 в столбик. Конечно, данную операцию легко произвести в уме или по таблице умножения, однако провести подробный разбор будет полезно для наглядности, хоть мы и так знаем, что 8 ÷ 2 = 4 .

Итак, сначала запишем делимое и делитель согласно методу деления в столбик.

Следующим шагом нужно выяснить, сколько делителей содержит делимое. Как это сделать? Последовательно умножаем делитель на 0 , 1 , 2 , 3 . . Делаем это до тех пор, пока в результате не получится число, равное или большее, чем делимое. Если в результате сразу получается число, равное делимому, то под делителем записываем то число, на которое умножали делитель.

Иначе, когда получается число, большее чем делимое, под делителем записываем число, вычисленное на предпоследнем шаге.На место неполного частного записываем то число, на которое умножался делитель на предпоследнем шаге.

Вернемся к примеру.

2 · 0 = 0 ; 2 · 1 = 2 ; 2 · 2 = 4 ; 2 · 3 = 6 ; 2 · 4 = 8

Итак, мы сразу получили число, равное делимому. Записываем его под делимым, а число 4 , на которое мы умножали делитель, записываем на место частного.

Теперь осталось вычесть числа под делителем (также по методу столбика). В нашем случае 8 – 8 = 0 .

Данный пример – деление чисел без остатка. Число, получащееся после вычитания – это остаток деления. Если оно равно нулю, значит числа разделились без остатка.

Теперь рассмотрим пример, когда числа делятся с остатком. Разделим натуральное число 7 на натуральное число 3 .

В данном случае, последовательно умножая тройку на 0 , 1 , 2 , 3 . . получаем в результате:

3 · 0 = 0 7 ; 3 · 1 = 3 7 ; 3 · 2 = 6 7 ; 3 · 3 = 9 > 7

Под делимым записываем число , полученное на предпоследнем шаге. По делителем записываем число 2 – неполное частное, полученное на предпоследнем шаге. Именно на двойку мы умножали делитель, когда получили 6 .

В завершение операции вычитаем 6 из 7 и получаем:

Данный пример – деление чисел с остатком. Неполное частное равно 2 , а остаток равен 1 .

Теперь, после рассмотрения элементарых примеров, перейдем к делению многозначных натуральных чисел на однозначные.

Алгоритм деления столбиком будем рассматривать на примере деления многозначного числа 140288 на число 4 . Сразу скажем, что понять суть метода гораздо легче на практических примерах, и данный пример выбран не случайно, так как иллюстрирует все возможные нюансы деления натуральных чисел столбиком.

Алгоритм деления столбиком

1. Запишем числа вместе с символом деления столбиком. Теперь смотрим на первую слева цифру в записи делимого. Возможны два случая: число, определяемое этой цифрой, больше, чем делитель, и наоборот. В первом случае мы работаем с этим числом, во втором – дополнительно берем следующую цифру в записи делимого и работаем с соответствующим двузначным числом. Согласно с этим пунктом, выделим в записе примера число, с которым будем работать первоначально. Это число – 14 , так как первая цифра делимого 1 меньше, чем делитель 4 .

2. Определяем, сколько раз числитель содержится полученном числе. Обозначим это число как x = 14 . Последовательно умножаем делитель 4 на каждый член ряда натуральных чисел ℕ , включая нуль : 0 , 1 , 2 , 3 и так далее. Делаем это, пока не получим в результате x или число, большее чем x . Когда в результате умножения получается число 14 , записываем его под выделенным числом по правилам записи вычитания в столбик. Множитель, на который умножался делитель, записываем под делітелем. Если в результате умножения получается число, большее чем x , то под выделенным числом записываем число, полученное на предпоследнем шаге, а на место неполного частного (под делителем) пишем множитель, на который на предпоследнем шаге проводилось умножение.

В соответствии с алгоритмом имеем:

4 · 0 = 0 14 ; 4 · 1 = 4 14 ; 4 · 2 = 8 14 ; 4 · 3 = 12 14 ; 4 · 4 = 16 > 14 .

Под выделенным числом записываем число 12 , полученное на предпоследнем шаге. На место частного записываем множитель 3 .

3. Столбиком вычитаем из 14 12 , результат записываем под горизонтальной чертой. По аналогии с первым пунктом сравниваем полученное число с делителем.

4. Число 2 меньше числа 4 , поэтому записываем под горизонтальной чертой после двойки цифру,расположенную в следующем разряде делимого. Если же в делимом более нет цифр, то на этом операция деления заканчивается. В нашем примере после полученного в предыдущем пункте числа 2 записываем следубщую цифру делимого – 0 . В итоге отмечаем новое рабочее число – 20 .

Пункты 2 – 4 повторяются циклически до окончания операции деления натуральных чисел столбиком.

2. Снова посчитаем, сколько делителей содержится в числе 20 . Умножая 4 на 0 , 1 , 2 , 3 . . получаем:

Так как мы получили в результе число, равное 20 , записываем его под отмеченным числом, а на месте частного, в следубщем разряде, записываем 5 – множитель, на который проводилось умножение.

3. Проводим вычитание столбиком. Так как числа равны, получаем в результате число ноль: 20 – 20 = 0 .

4. Мы не будем записывать число ноль, так как данный этап – еще не окончание деления. Просто запомним место, куда мы могли его записать и запишем рядом число из следующего разряда делимого. В нашем случае – число 2 .

Принимаем это число за рабочее и снова выполняем пункты алгоритма.

2. Умножаем делитель на 0 , 1 , 2 , 3 . . и сравниваем результат с отмеченным числом.

4 · 0 = 0 2 ; 4 · 1 = 4 > 2

Соответственно, под отмеченным числом записываем число 0 , и под делителем в следующий разряд частного также записываем 0 .

3. Выполняем операцию вычитания и под чертой записываем результат.

4. Справа под чертой добавляем цифру 8 , так как это следующая цифра делимого числа.

Таким образом, получаем новое работчее число – 28 . Снова повторяем пункты алгоритма.

Проделав все по правилам, получаем результат:

Переносим под черту вниз последнюю цифру делимого – 8 . В последний раз повторяем пункты алгоритма 2 – 4 и получаем:

В самой нижней строчке записываем число 0 . Это число записывается только на последнем этапе деления, когда операция завершена.

Таким образом, результатом деления числа 140228 на 4 является число 35072 . Данный пример разобран очень подробно, и при решении практических заданий расписывать все действия столь досканально не нужно.

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

Пример 1. Деление натуральных чисел в столбик

Разделим натуральное число 7136 на натуральное число 9 .

После второго, третьего и четвертого шага алгоритма запись примет вид:

Последний проход, и поучаем результат:

Ответ: Неполное неполное частное чисел 7136 и 9 равно 792 , а остаток равен 8 .

При решении практических примеров в иделе вообще не использовать пояснения в виде словесных комментариев.

Пример 2. Деление натуральных чисел в столбик

Разделим число 7042035 на 7 .

Деление многозначных натуральных чисел столбиком

Алгоритм деления многозначных чисел в столбик очень похож на рассмотренный ранее алгорим деления многозначного числа на однозначное. Если быть точнее, изменения касаются только первого пункта, а пункты 2 – 4 остаются неизменными.
Если при делении на однозначное число мы смотрели только на первую цифру делимого, то теперь будем смотреть на столько цифр, сколько есть в делителе.Когда число, определяемое этими цифрами, больше делителя, принимам его за рабочее число. Иначе – добавляем еще одну цифру из следующего разряда делимого. Затем следуем пунктам описанного выше алгоритма.

Рассмотрим применение алгоритма деления многозначных чисел на примере.

Пример 3. Деление натуральных чисел в столбик

Разделим 5562 на 206 .

В записи делителя участвуют три знака, поэтому в делимом сразу выделим число 556 .
556 > 206 , поэтому принимаем это число за рабочее и переходим к пункту 2 аглоритма.
Умножаем 206 на 0 , 1 , 2 , 3 . . и получаем:

206 · 0 = 0 556 ; 206 · 1 = 206 556 ; 206 · 2 = 412 556 ; 206 · 3 = 618 > 556

618 > 556 , поэтому под делителем записываем результат предпоследнего действия, а под делимым – множитель 2

Выполняем вычитание столбиком

В результате вычитания имеем число 144 . Справа от результата под чертой записываем число из соответствующего разряда делимого и получаем новое рабочее число – 1442 .

Повторяем с ним пункты 2 – 4 . Получаем:

206 · 5 = 1030 1442 ; 206 · 6 = 1236 1442 ; 206 · 7 = 1442

Под отмеченным рабочим числом записываем 1442 , а в следующий разряд частного записываем цифру 7 – множитель.

Выполняем вычитание в столбик, и понимаем, что на этом операция деления окончена: в делителе более нет цифр, чтобы записать их правее от результата вычитания.

В завершение данной темы приведем еще один пример деления многозначных чисел в столбик, уже без пояснений.

Пример 5. Деление натуральных чисел в столбик

Длинная арифметика — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.

Виды целочисленной длинной арифметики

Вообще говоря, даже только в олимпиадных задачах набор средств достаточно велик, поэтому произведём классификацию различных видов длинной арифметики.

Классическая длинная арифметика

Основная идея заключается в том, что число хранится в виде массива его цифр.

Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), либо двоичная система счисления.

Операции над числами в этом виде длинной арифметики производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком. Впрочем, к ним также применимы алгоритмы быстрого умножения: Быстрое преобразование Фурье и Алгоритм Карацубы.

Здесь описана работа только с неотрицательными длинными числами. Для поддержки отрицательных чисел необходимо ввести и поддерживать дополнительный флаг "отрицательности" числа, либо же работать в дополняющих кодах.

Структура данных

Хранить длинные числа будем в виде вектора чисел , где каждый элемент — это одна цифра числа.

Для повышения эффективности будем работать в системе по основанию миллиард, т.е. каждый элемент вектора содержит не одну, а сразу цифр:

Цифры будут храниться в векторе в таком порядке, что сначала идут наименее значимые цифры (т.е. единицы, десятки, сотни, и т.д.).

Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.

Вывод

Самое простое — это вывод длинного числа.

Сначала мы просто выводим самый последний элемент вектора (или , если вектор пустой), а затем выводим все оставшиеся элементы вектора, дополняя их нулями до символов:

(здесь небольшой тонкий момент: нужно не забыть записать приведение типа , поскольку в противном случае число будут беззнаковым, и если , то при вычитании произойдёт переполнение)

Чтение

Считываем строку в , и затем преобразовываем её в вектор:

Если использовать вместо массив ‘ов, то код получится ещё компактнее:

Если во входном числе уже могут быть лидирующие нули, то их после чтения можно удалить таким образом:

Сложение

Прибавляет к числу число и сохраняет результат в :

Вычитание

Отнимает от числа число () и сохраняет результат в :

Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.

Умножение длинного на короткое

Умножает длинное на короткое () и сохраняет результат в :

Здесь мы после выполнения деления удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.

(Примечание: способ дополнительной оптимизации. Если скорость работы чрезвычайно важна, то можно попробовать заменить два деления одним: посчитать только целую часть от деления (в коде это переменная ), а затем уже посчитать по ней остаток от деления (с помощью одной операции умножения). Как правило, этот приём позволяет ускорить код, хотя и не очень значительно.)

Умножение двух длинных чисел

Умножает на и результат сохраняет в :

Деление длинного на короткое

Делит длинное на короткое (), частное сохраняет в , остаток в :

Длинная арифметика в факторизованном виде

Здесь идея заключается в том, чтобы хранить не само число, а его факторизацию, т.е. степени каждого входящего в него простого.

Этот метод также весьма прост для реализации, и в нём очень легко производить операции умножения и деления, однако невозможно произвести сложение или вычитание. С другой стороны, этот метод значительно экономит память в сравнении с "классическим" подходом, и позволяет производить умножение и деление значительно (асимптотически) быстрее.

Этот метод часто применяется, когда необходимо производить деление по непростому модулю: тогда достаточно хранить число в виде степеней по простым делителям этого модуля, и ещё одного числа — остатка по этому же модулю.

Длинная арифметика по системе простых модулей (Китайская теорема или схема Гарнера)

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

Как утверждает Китайская теорема об остатках, этого достаточно, чтобы однозначно хранить любое число в диапазоне от 0 до произведения этих модулей минус один. При этом имеется Алгоритм Гарнера, который позволяет произвести это восстановление из модульного вида в обычную, "классическую", форму числа.

Таким образом, этот метод позволяет экономить память по сравнению с "классической" длинной арифметикой (хотя в некоторых случаях не столь радикально, как метод факторизации). Крому того, в модульном виде можно очень быстро производить сложения, вычитания и умножения, — все за асимптотически однаковое время, пропорциональное количеству модулей системы.

Однако всё это даётся ценой весьма трудоёмкого перевода числа из этого модульного вида в обычный вид, для чего, помимо немалых временных затрат, потребуется также реализация "классической" длинной арифметики с умножением.

Помимо этого, производить деление чисел в таком представлении по системе простых модулей не представляется возможным.

Виды дробной длинной арифметики

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

Длинная арифметика в несократимых дробях

Число представляется в виде несократимой дроби , где и — целые числа. Тогда все операции над дробными числами нетрудно свести к операциям над числителями и знаменателями этих дробей.

Обычно при этом для хранения числителя и знаменателя приходится также использовать длинную арифметику, но, впрочем, самый простой её вид — "классическая" длинная арифметика, хотя иногда оказывается достаточно встроенного 64-битного числового типа.

Выделение позиции плавающей точки в отдельный тип

Иногда в задаче требуется производить расчёты с очень большими либо очень маленькими числами, но при этом не допускать их переполнения. Встроенный -байтовый тип , как известно, допускает значения экспоненты в диапазоне , чего иногда может оказаться недостаточно.

Приём, собственно, очень простой — вводится ещё одна целочисленная переменная, отвечающая за экспоненту, а после выполнения каждой операции дробное число "нормализуется", т.е. возвращается в отрезок , путём увеличения или уменьшения экспоненты.

При перемножении или делении двух таких чисел надо соответственно сложить либо вычесть их экспоненты. При сложении или вычитании перед выполнением этой операции числа следует привести к одной экспоненте, для чего одно из них домножается на в степени разности экспонент.

Наконец, понятно, что не обязательно выбирать в качестве основания экспоненты. Исходя из устройства встроенных типов с плавающей точкой, самым выгодным представляется класть основание равным .