Предисловие [Длинная арифметика]

[Вся длинная арифметика] 

Итак мы начинаем разговор о длинной арифметике.
Под длинной арифметикой мы, как и все, будем понимать математические действия над числами, которые по своему размеру превышают ограничения стандартных типов данных. Так например в тип int(4 байта) уместиться число 2^31 = 2147483648 (~2e9), в unsigned int(те же 4 байта) – число 2^32 = 4294967296 (~4e9). В переменную типа long long или __int64(8 байт) “влезет” 2^63 = 9223372036854775808 (~9e18), в безнаковый тип в два раза больше (~1e19). Как мы видим, уже для чисел в 25 разрядов в десятичной системе счисления нет типа в 32 разрядной системе, который бы удовлетворял нашим нуждам. Как быть? Ведь на практике встречаются числа с куда большим количеством разрядов. Унывать не стоит! Предки уже решили эту проблему за нас. Нам остается просто научиться делать тоже самое и не изобретать велосипед. Хотя крайне полезно сперва его изобрести и попытаться самостоятельно решить возникшие в результате проблемы.

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

Теория:
* Первая глава книги Окулова “Программирование в алгоритмах”.
* Раздел 4 Дистанционная подготовка по информатике
* e-maxx

Практика: Дистанционная подготовка

Условные обозначения:
* osn – основание системы счисления 
* A,B – “длинные” числа
* n – “короткое”, 0 <= n < osn

Предисловие
Основные операции:
* Ввод
* Вывод 
* A + n
* Сравнение
* A + B
* A – B (A >= B)
* A – B (со знаком)
* A * n
* A * B
* A / n, A % n 
* A / B, A % B

Дополнительные операции:
* A^n
* n!
* sqrt(A)
* N^N mod 10^P

Экзотика:
* A – n

Тренировка #4 [Меньшиков]

[Условия задач]                   [Список тренировок] 

4A. Совершенные числа
[perfect]
Хорошая несложная задача. Есть один подвох, на который натыкаются многие. Желаю наткнуться на него всем начинающим, чтобы глубже проникнуться задачей. 
4B. Разложение на слагаемые
[decomp]
Компактная рекурсивная реализация. В ходе решения встает только одна проблема: как не генерировать комбинации слагаемых, которые уже были до этого? Для этого, по рекомендации Меньшикова, условимся, что в получаемой комбинации предыдущее слагаемое не превышает текущего. Этим приемом можно пользоваться и в других подобных задачах для обеспечения уникальности последовательностей.

Тренировка #3 [Меньшиков]

[Условия задач]                   [Список тренировок]

3A.Разложение на простые множители
[pfactor] Типовая соптимизированная реализация
Оптимизация заключается в пересчете верхней границы цикла(корень квадратный из N) при переходе к новому делителю.
3B.Перестановки(2)
[permut2] Рекурсивная реализация с подсчетом элементов
Реализация основана на разборе этой задачи из книги Меньшикова. Первоначально подсчитываем количество вхождений символов из первоначальной перестановки. Затем на i-ое место текущей перестановки ставим ближайший в лексикографическом порядке символ, счетчик которого имеет ненулевое значение, и декрементируем счетчик на единицу.
[permut2] Идентично [permut] next_permutation
Важный факт того, что генерация алгоритмом next_permutation не зависит от того есть ли дублирующие символы во входном наборе или нет. Общий вывод: любая корректная реализация задачи 3B пройдет на задаче 2B.

1018. Двоичная яблоня (ДП, структура данных) [acm.timus.ru]

[Условие]

Основная идея:
В ходе решения встают следующие вопросы:
1) Как хранить дерево?
2) Как его получить, используя входные данные?
3) Что дальше делать с этим деревом?

1002. Телефонные номера (ДП) [acm.timus.ru]

[Условие]

Основная идея:
Всю задачу можно разделить на 3 этапа:
1) Хранение данных
Каждое слово из словаря необходимо хранить как в цифровом, так и в буквенном варианте. Для слова “our” цифровое представление будет равно “087”. При этом необходимо иметь связь между между обоими представлениями для получения ответа. Один из вариантов хранения такого представления можно описать в виде структуры, а весь словарь в виде массива элементов таких структур:

1. struct word
2. {
3.   string str;      // буквенное представление
4.   string digits;   // цифровое представление
5. };
6. vector<word> dict; // словарь

Задачи с acm.timus.ru

1002. Телефонные номера (ДП)
1015. Найдите различия! (сортировка,STL, пространственное воображение)
1017. Лестницы (комбинаторика, ДА)
1018. Двоичная яблоня (ДП, структура данных)
1019. Перекрашивание прямой (сортировка, структура данных)
1022. Генеалогическое дерево (топологическая сортировка)