Problem link?

In the code of the first submission, try changing res = res + line by res += line.

Just a tiny correction, if I understood it correctly; you said: "So the challenge is to find an assignment of wagons to locomotives such that minimizes the longest train (locomotive + wagons) forwarded to A (trains sent to B don't matter, you can send huge trains to B and their lengths would be ignored)". The locomotive doesn't count, only the wagons.

About the solution per se, I thought about some binary search on the number of vagons, i.e. the answer itself. How? Let's suppose we have a value X and we are able to verify whether it is possible to assign at most X wagons to any of the L locomotives heading to target A. If we have such method, then it's clear that is possible to assign at most X + 1 or X + 2 or X + 3 (and so on) wagons to the L locomotives.

Now, how to create such method to verificate whether, given the so called value X, it is possible to find a correct assignment? I thought something like this: we will create a variable called left, which will represent the first wagon to be assigned to the current locomotive, and a variable called used, which will represent how many locomotives we have used so far. Now, we start iterating over the array of wagons containing freight; whenever we find a value W[i] that makes W[i] - left + 1 > X, it means that left and W[i] cannot be carried by the same locomotive. Thus, in order to be optimal, we will find the greatest value j that is less than W[i] which obeys the condition j - left + 1 = X (it can be done with simple math). When we find such j, we need to update our left variable to j + 1 (i.e. the first wagon to be taken is the next one) and increment our variable used. Note that if there is no wagon with freight between left and the W[i] that 'breaks' the condition, then the value j is simply W[i] - 1, because doesn't matter how many empty wagons we take when we are heading to point B. Finally, after all the wagons have been assigned to some locomotive, the answer to the question "is it possible to assign the wagons to the L locomotives such that the locomotives heading to point A will have at most X wagons assigned to?" is simply given by the condition used <= L. I.e., if it is true, then the answer is yes; otherwise, it is no.

I didn't actually code this problem, so I may have committed some mistake in the above thinking. Feel free to criticize.

In problem E, why can't we use the euclidean algorithm to find the gcd between d and a[i]?

Hi. Can you, please, share the problem's link?

Thanks!

Nice one too!! Thank you!!

Thank you!!!

Why do we need to sum up phi[M] in A ^ (x % phi [M] + phi [M]) % m? Isn't A ^ (x % phi[M]) % m good enough?