This is ridiculous!!
My AC solution (ACed twice) works in 0.950 seconds. Which is actually O(n^2). The code is long and nasty... After some "improvements" - ie changing ArrayList to LinkedList/getting rid off BitSet/etc - the running time should decrease drastically!! but it gives me TL... WTF?
I was sure, that my "better" code works FASTER, since there is much less operations to perform...
Can anyone help me with it? I can send the code to get feedback.
Thanks!

And I'm interesting how to solve this in 0,015s.

well...
There's good idea in neighbor thread, which proves that solution always exist. It can help you solve it in O(n).
Or... you can think up your own ideas based on remainders... There's up to N remainders only... so I used BFS without considering duplicates... it works fast enough in Java.

Yeah, there is a nice idea. =)

0.14 seconds on JAVA, O(nlogn + n) solution