N^N mod 10^P

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

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

По условию задачи 1<=N<=1e9 и 1<=P<=100.

Квадратный корень из длинного числа

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

Эта задача далась мне тяжелее всех. Наверное потому, что я пытался зачесть ее на acm.sgu.ru и acmp.ru, где ограничения на количество разрядов в числе 1000 и 3000 соответственно. Для начала зачтем эту задачу на informatics.mccme.ru, где ограничение всего 100.

Здесь можно пойти двумя путями:

Длинное - короткое

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

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

Приведенная реализация практически идентична с  реализацией операции “длинное + короткое”:

1. BigInt operator - (const BigInt &a, const int &b)
2. {
3.   BigInt res = a;
4.   int pos = 0;
5.   res.digits[0] -= b;
6.   while (res.digits[pos] < 0)
7.   {
8.     res.digits[pos+1] --;
9.     res.digits[pos++] +=osn;
10.   }
11.   if (res.amount && !res.digits[res.amount-1])
12.     res.amount--;
13.   return res;
14. }

* This source code was highlighted with Source Code Highlighter.

Факториал короткого числа

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

Тип int может поместить в себя не больше 12!.А как же нам быть если нужно найти 100! ? Самое время обратиться к длинной арифметике.
Сама реализация не представляет для нас ничего нового:

1. BigInt fact(int n)
2. {
3.   BigInt res(1);
4.   for (int i=2;i<=n;i++)
5.     res = res * i;
6.   return res;
7. }

* This source code was highlighted with Source Code Highlighter.

По условию задачи n<=3000. В качестве osn лучше выбрать 10000, т.к. в таком случае мы сможем обойтись умножением длинного на короткое.

Длинное^короткое (возведение в степень)

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

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

1. BigInt pow(const BigInt &a, const int &N)
2. {
3.   BigInt res(1),cur = a;
4.   int n = N;
5.   while (n)
6.   {
7.     if (n&1)
8.       res = res * cur;
9.     cur = cur * cur;
10.     n>>=1;
11.   }
12.   return res;
13. }

* This source code was highlighted with Source Code Highlighter.

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

Длинное DIV длинное & Длинное MOD длинное

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

Пришло время познакомиться с самой “страшной” операцией на длинную арифметику. Первый раз я ее реализовал на Accepted 31 июля 2008. До этого момента мне было даже страшно подумать над ее реализацией. Но как оказалось не так уж это деление и страшно, как его малюют. Мы не будем изобретать велосипед, а просто грамотно, максимально понятно и быстро реализуем деление столбиком. Рассмотрим нижепредставленный рисунок.

Как видно osn = 100.

Длинное DIV короткое & Длинное MOD короткое

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

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

Длинное * длинное

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

Итак мы подошли к первой операции, реализацию которой можно считать не такой тривиальной, как в предыдущих случаях:

1. BigInt operator * (const BigInt &a, const BigInt &b)
2. {
3.   BigInt res;
4.   for (int i=0;i<a.amount;i++)
5.   {
6.     int r = 0;
7.     for (int j=0;j<b.amount | r;j++)
8.     {
9.       res.digits[i+j] += a.digits[i] * b.digits[j] + r;
10.       r = res.digits[i+j] / osn;
11.       res.digits[i+j] -= r*osn;
12.     }
13.   }
14.   int pos = a.amount + b.amount;
15.   while (pos>0 && !res.digits[pos])
16.     pos--;
17.   res.amount = pos + 1;
18.   return res;
19. }

* This source code was highlighted with Source Code Highlighter.

Обратим внимание на строчку 11. Т.к. алгоритм квадратичный, то избежание использования операции взятия остатка от деления(%) дает прирост в скорости, более ощутимый, чем для линейных алгоритмов.

Длинное * короткое

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

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

1. BigInt operator * (const BigInt &a, const int &n)
2. {
3.   BigInt res;
4.   res.amount = a.amount;
5.  
6.   int r = 0;
7.   for (int i=0;i<res.amount | r;i++)
8.   {
9.     res.digits[i] = a.digits[i] * n + r;
10.     r = res.digits[i]/osn;
11.     res.digits[i] -= r*osn;
12.   }
13.   if (res.digits[res.amount])
14.     res.amount++;
15.  
16.   return res;
17. }

* This source code was highlighted with Source Code Highlighter.

Как видно алгоритм линейный. Для ускорения операций в строке 11 мы избежали использования операции взятия остатка от деления(%).

Длинное – длинное(знаковое вычитание)

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

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

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

Имея в наличии реализации всех операций в неотрицательных числах можно реализовать их и с учетом знака.

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

1. bool isMinus = false;
2. if (a < b)
3. {
4.   c = b - a;
5.   isMinus = true;
6. }
7. else
8.   c = a - b;
9. if (isMinus) cout<<"-";
10. c.output();

* This source code was highlighted with Source Code Highlighter.

Длинное – длинное (беззнаковое вычитание)

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

Рассмотрим случай беззнакового вычитания, когда вычитаемое не превосходит уменьшаемого(A-B, A>=B):

1. BigInt operator - (const BigInt &a, const BigInt &b)
2. {
3.   BigInt res = a;
4.   int r = 0;
5.   for (int i = 0;i<res.amount;i++)
6.   {
7.     res.digits[i] -= b.digits[i] + r;
8.     if (res.digits[i]<0)
9.     {
10.       res.digits[i]+=osn;
11.       res.digits[i+1]--;
12.     }   
13.   }
14.   int pos = res.amount;
15.   while (pos && !res.digits[pos])
16.     pos--;
17.   res.amount = pos+1;
18.   return res;
19. }

* This source code was highlighted with Source Code Highlighter.

В реализации данной операции необходимо корректно учесть случай, когда a=b.

P.S: В первой версии выводились лишние ведущие нули. Эту ошибку обнаружил Privalov, за что выражаю ему благодарность.

Сравнение длинных чисел

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

Чтобы сравнить длинные числа необходимо и достаточно определить три операции: “больше”, “меньше” и “проверка на равенство”. Отметим важный факт: для реализации задуманного можно реализовать только только одну операцию (или “больше” или “меньше”). Остальные можно выразить из нее.

Длинное + короткое

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

Более распространенной операцией сложения является операция “Длинное + длинное”. Если имеем дело с частным случаем, когда одно из слагаемых является длинным числом, а второе строго меньше основания системы счисления (<osn), т.е. является цифрой, то в целях оптимизации и ускорения работы программы следует подумать над более быстрой реализацией.

Представляю свою реализацию:

1. BigInt operator + (const BigInt &a, const int &b)
2. {
3.   BigInt res = a;
4.   int pos = 0;
5.   res.digits[0] += b;
6.   while (res.digits[pos]>=osn)
7.   {
8.     res.digits[pos+1]++;
9.     res.digits[pos++]-=osn;
10.   }
11.   if (res.digits[res.amount])
12.     res.amount++;
13.   return res;
14. }

* This source code was highlighted with Source Code Highlighter.

Практически идентичную реализацию имеет и операция “длинное – короткое”.

Вывод длинных чисел

[Вся длинная арифметика]
Вывод длинных чисел тесно связан с вводом). Опять же рассмотрим два случая для osn = 10 и для osn = 10000.

Первый случай:

1. void output()
2. {
3.   for (int i=amount-1;i>=0;i--)
4.     cout<<digits[i];
5. }

* This source code was highlighted with Source Code Highlighter.

Второй случай:

1. int len = 4;
2. const char * digitFormat = "%.4d";
3. ...
4. void output()
5. {
6.   printf("%d",digits[amount-1]);
7.   for (int i= amount-2;i>=0;i--)
8.     printf(digitFormat,digits[i]);
9. }

* This source code was highlighted with Source Code Highlighter.

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

Ввод длинных чисел

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

Рассмотрим два случая считывания длинных чисел. Первый случай(базовый), при котором osn = 10. Во втором, в качестве osn выберем одну из степеней десятки. Забегая вперед отмечу факт, что эту степень нужно выбирать очень аккуратно, чтобы избежать переполнения при реализации операций. Так например, если цифра длинного числа хранится в int’е и мы реализуем операцию плюс, то максимально возможная степень десятки у osn будет 9. (В умных книжках обычно после подобных фраз пишут: “Почему?”). Если же реализуем операцию умножения длинного на длинное, то максимальный osn = 1e4. С учетом всего вышесказанного давайте ознакомимся с возможной реализацией первого случая:

Длинное + длинное

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

Операция сложения двух длинных чисел:

1. BigInt operator + (const BigInt &a, const BigInt &b)
2. {
3.   BigInt res;
4.   res.amount = max(a.amount,b.amount);
5.   int r = 0;
6.   for (int i=0;i<res.amount | r;i++)
7.   {
8.     res.digits[i] = a.digits[i] + b.digits[i] + r;
9.     if (res.digits[i]>=osn)
10.     {
11.       res.digits[i]-=osn;
12.       r = 1;
13.     }
14.     else
15.       r = 0;
16.   }
17.   if (res.digits[res.amount])
18.     res.amount++; 
19.  
20.   return res;
21. }

* This source code was highlighted with Source Code Highlighter.

В данной реализации отсутствует операция взятия остатка от деления. Вместо этого используется вычитание значения основания системы счисления в строке 11.

P.S: Данная реализация появилась на основе статьи Виталия Гольдштейна с учетом оформления длинных чисел команды HotFinnKeys.

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

Теория:
* Первая глава книги Окулова “Программирование в алгоритмах”.
* Раздел 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