A very nice thing happend to me! When I used long arithmetic with base 10^17 I got TL many times. Even after I made my program calculate an expression like (2^N * 3^M) only one time! (I didn't use fast power). Then I generally rewrote my class BigInteger, and now it can calculate the product of two big numbers :) So I used the "fast-power" algo, and after this I immediately got AC in 0.156s.

It should be noted that now I use base = 10^9 and store the numbers in vector (earlier they were stored in arrays). Of course, these "upgrades" make this class work slower and use more memory. But my program uses only ~700 KB of memory (it was another surprise for me). The only thing I did to make my program faster was use the algo written above. I didn't expect it would work much faster...

So, fast power RULEZZZ! :D

Edited by author 27.09.2010 01:39