|
|
back to boardIs it possible to solve this problem without long arithmetic? If no, please, tell me, where can I find class BigInteger. Such one, that I wrote myself, works too slow :( Re: Is it possible to solve this problem without long arithmetic? I think it's possible to solve it without BigNum.The question asks you to mod m...so it can't be over m Re: Is it possible to solve this problem without long arithmetic? 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 Re: Is it possible to solve this problem without long arithmetic? 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. Re: Is it possible to solve this problem without long arithmetic? It can be even solved in O( lg(p) + ln(n) ) |
|
|