Discussion @ 1926. The Tournament of Intelligences @ Timus Online Judge

TLE 13: How to optimize?

Posted by Nodir NAZAROV Komiljonovich 4 Feb 2014 03:09

Brute-force approach using BigInteger in Java exceeds time limit in test#13. Can anybody give a hint, please?

Thanks.

Re: TLE 13: How to optimize?

Posted by Nodir NAZAROV Komiljonovich 4 Feb 2014 03:19

I know there are some rules for modulo by 3 or 5. I'm not sure applying only those two rules will help. Or are there are generic rule for modulo by prime numbers?

Edited by author 04.02.2014 03:20

Re: TLE 13: How to optimize?

Posted by Nodir NAZAROV Komiljonovich 4 Feb 2014 03:23

Ok, I got something: this article will help, I guess
http://www.maths.ox.ac.uk/files/imported/prospective-students/undergraduate/sutton/lecture2.pdf

Edited by author 04.02.2014 03:23

Re: TLE 13: How to optimize?

Posted by mikroz 28 Jul 2014 22:19

Chinese Remainder Theorem does the trick.

Discussion of Problem 1926. The Tournament of Intelligences