N^N mod 10^P

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

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

По условию задачи 1<=N<=1e9 и 1<=P<=100. Таким образом заведем длинное число, которое проинициализируем числом N. Реализуем быстрое возведение в степень. При этом умножение длинных чисел будем осуществлять не целиком, а только до разряда не превышающего P. Изложенная логика представлена ниже:

1. BigInt powNmod10powP(int n, int p)
2. {
3.     BigInt res(1);
4.     BigInt cur = *this;
5.     P = p;
6.     while (n)
7.     {
8.       if (n&1)
9.         res = res * cur;
10.       cur = cur * cur;
11.       n/=2;
12.     }
13.     return res;
14. }
15. ...
16. int BigInt::P;
17. BigInt operator * (const BigInt &a, const BigInt &b)
18. {
19.   BigInt res;
20.   for (int i=0;i<a.amount;i++)
21.   {
22.     int r = 0;
23.     for (int j=0;j<b.amount | r;j++)
24.     {
25.       // блокируем просчет более старших разрядов
26.       // эффект this = this % 10^P
27.       if (i+j >= BigInt::P)
28.         break;
29.  
30.       res.digits[i+j] += a.digits[i] * b.digits[j] + r;
31.       r = res.digits[i+j] / osn;
32.       res.digits[i+j] -= r*osn;
33.     }
34.   }
35.   int pos = a.amount + b.amount;
36.   while (pos>0 && !res.digits[pos])
37.     pos--;
38.   res.amount = pos + 1;
39.   return res;
40. }

* This source code was highlighted with Source Code Highlighter.

Полный исходный код можно посмотреть здесь