How to solve this problem efficiently http://main.edu.pl/en/archive/oi/10/sum ? The time limit is 1 s (for 100 p) and the grading machines are quite slow.
In Looking for a Challenge there is a solution which time complexity is O(a_1*n*log(a_1)), but with a1 = 50000 and n = 5000 I don't think the solution is fast enough.
Also here: http://www.oi.edu.pl/old/download/oi10.pdf the time complexity seems to be something similar, though I don't know Polish so I'm not sure.
I came up with a bit different solution O(a_n*n) (also considering a graph but now with a_n nodes and edges with length of 1 and 0 depending if the go past the 0 mod a_n or not. I don't think it is important to describe the solution more here.) solution and also a O(a_n*a_n/32) solution using bitwise operations. But the first solution is too slow and I don't think the problem should be solved using bitwise operations.
Here is the solution in Looking for a Challenge:
Consider a graph with nodes representing values mod a_1. Then we want to find the shortest path to each node from node 0 mod a_1. This can be done using Dijkstra's algorithm.
Maybe there is again some trivial thing that I cannot see...