Discussion @ 1749. Periodic Sum @ Timus Online Judge

Is it possible to solve this problem without long arithmetic?

Posted by bsu.mmf.team 19 Feb 2010 00:51

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?

Posted by MeLodyloveyr 25 Feb 2010 04:57

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?

Posted by bsu.mmf.team 3 Mar 2010 11:00

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?

Posted by SkidanovAlex 21 Apr 2010 03:08

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?

Posted by Nemanja Skoric 23 May 2010 07:14

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

Discussion of Problem 1749. Periodic Sum