I solve the problem on E-Olymp .

My code is:

int _tmain(int argc, _TCHAR* argv[]) { double n, kol = 1, sum = 0; cin >> n; for (int i = 0; i < (n*n); i++) { sum += kol; kol *= 2; } printf("%.0f\n", sum); system("pause"); return 0; }

The site checks for an input value of 10. double , as I understand it, is not an assistant for this because it is limited. Please tell me how to implement?

  • one
    In the column in the school to multiply the numbers you are not taught? That's right, so the algorithm for multiplying two numbers and paint. And the result is recorded in the form of a normal line. - Max ZS
  • one
    Change language to Java for this task ... - Qwertiy ♦
  • one
    e-maxx.ru/algo/big_integer - Qwertiy ♦
  • @Qwertiy And what Java will give? - Max ZS
  • @MaxZS, BigInteger is built in there. - Qwertiy ♦

1 answer 1

From the principle I had to solve the problem, it passed, I even whistled to second place :) very quickly.

We can accurately estimate the maximum size of a number, so we know what data array we need. I went on the way N*N doubling, followed by subtraction 1. We need only two operations - doubling and subtracting 1. We take an array of 350 (with a margin) unsigned long , and N*N times we double it (we add the corresponding elements, if need to transfer). To quickly convert to decimal - in each element of the array, the values ​​are limited to one billion. I keep track of the size of the number - so as not to summarize the extra ...

Of course, I can give the code here, but I'm not sure how good it is in the pedagogical sense :) I’ll show a little bit though.

 class bigNum { public: bigNum() { a[0] = 1; } void mul2(); void dec() { a[0]--; } void out(); private: static const int size = 350; static const int lim = 1000000000; unsigned long a[size] = { 0 }; int last = 1; }; void bigNum::mul2() { unsigned long carry = 0; for(int i = 0; i < last; ++i) { a[i] *= 2; a[i] += carry; if (a[i] >= lim) { carry = a[i]/lim; a[i] %= lim; } else carry = 0; } if (carry) { a[last++] = carry; } };

PS To increase the speed, you can multiply, say, by 16 or 64 there, by changing the size accordingly ...

  • dec() will not work if a[0] == 0 - int3
  • @ int3 By the condition of the problem - 2^N-1 - this is impossible, isn't it? :) - Harry
  • the class is still called bigNum , not solver ;) For the task it doesn’t matter, yes - int3
  • The conditional statement in the loop is superfluous, it only slows down. But, generally speaking, then we must then use the quick exponentiation ... - Pavel Mayorov