суббота, 11 сентября 2010 г.

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.

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

Комментариев нет:

Отправить комментарий