If you use newton's method to find a square root make sure that your division algorithm for 2 big integers is fast enough to handle quickly a lot of divisions that requires newtons method, otherwise you will get TL ... even with O(n*log(BASE)) time complexity division algorithm your going to get TL.
Faster division at O(n) is described in Knuth's The Art of Computer Sience 2 edition, page 298 or 299...

So in case if yo get TL with newton's method (which has got actually better time complexity than binary search root finding) just use binary search algo for root with BASE = 10^9 for you big integers, it needs only division by 2, *, +, and - operations needed for big integer.
If input contains 600 digits you will only need 600 / 9 array elements to store that number ... and with less divisions you will get AC!

take care ...

Edited by author 09.07.2015 18:17