ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1749. Periodic Sum

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) )