If no, please, tell me, where can I find class BigInteger. Such one, that I wrote myself, works too slow :(

I think it's possible to solve it without BigNum.The question asks you to mod m...so it can't be over m

Yes, but the number p can be too big, and it's impossible to calculate the answer faster, than O(n^2), where n = [lg(p)], i.e. it is a very slow method. Does anybody know faster one?

Edited by author 20.03.2010 02:31

It is possible to solve this problem in O(lg(p) * ln(n)).
And you don't need long arithmetic, just do all the computations modulo p. 64 bit integer is enough in this case.

It can be even solved in O( lg(p) + ln(n) )