Max-flow algorithms usually work much faster than their advertised complexity. In general, it's pretty difficult to make a max-case for them.

If I recall correctly in that problem it's the same thing as I noted in last educational's problem F. Each path saturates one source/sink edge so the complexity is actually O(V*E) for these graphs. Now, a graph for a certain prime obviously has O(M + number of occurences of this prime * log) edges and the number of paths found is O(number of occurences of this prime) so in the end the complexity of the solution is actually O(N*log^3*M) for the dumb editorial solution, O(N*log^2*M) if you remove that *log from the editorial solution number of edges or O(N*max_number_of_primes(A)*M) if you code it like I did: https://codeforces.me/contest/498/submission/40045470

It's a bit different from what PurpleCrayon said. Yeah the tests might be bad but mostly these problems have some property in the network that makes it have better complexity and people cba to think about them.

ask maxflow about it