016.cpp

Go to the documentation of this file.

#include <iostream>
using namespace std;

const unsigned long long digits = 1e16;
const int gps = 19;
class bigN
{
//spilt into 16 groups, each with 19 digits
//smallest place unit exists in x[0]
  unsigned long long x[gps];
public:
    bigN (int init)
  {
    x[0] = init;
    for (int k = 1; k < gps; k++)
      x[k] = 0;
  }
  void times256 ()
  {
    for (int k = 0; k < gps; k++)
      x[k] *= 256;
    for (int k = 0; k < gps - 1; k++)
      if (x[k] > digits)
        {
          x[k + 1] += x[k] / digits;
          x[k] %= digits;
        }
  }
  unsigned sum_of_digits ()
  {
    unsigned long long y;
    unsigned sum = 0;
    for (int k = 0; k < gps; k++)
      {
        y = x[k];
        while (y != 0)
          {
            sum += y % 10;
            y /= 10;
          }
      }
    return sum;
  }
};

int
main ()
{
  bigN N (1);

//2^1000 = 256^125;
//so times 16 by 125 times
  for (int k = 1; k <= 125; k++)
    N.times256 ();

  cout << N.sum_of_digits () << endl;
  return 0;
}