To begin with, we will explain the solution of an easier version of this task, which appeared in the original Croatian edition of COCI, called HONI. The difference between this version and COCI's version is that in the easier version, the cuts had to be continuous (not interrupted).

First, we have to notice that, if the vertical part should be split into ~K~ parts, there must be ~K-1~ cuts on it, some of which were prolonged from previous vertical parts and some which have just started. The required solution is the sum of cuts which have just started for all vertical parts: this way, we count each cut exactly once – when we start it.

For each vertical part, we want to know the number of cuts prolonged from previous parts. Let us assume that the previous vertical part was cut into ~30~ parts and that the current vertical part should be cut into ~70~ parts. Both numbers are divisible by ~10~. This means that the first ~30~ parts can be seen as ~10~ large parts by ~3~, and the new ~70~ parts as ~10~ large parts by ~7~. The big parts match and the cuts between them can be prolonged. The number of those cuts is ~10-1 = 9~. The remaining ~69-9~ cuts should have to be started and added to the final solution.

We can deduce from this example that, in general, the number of cuts that can be prolonged from the part ~i~ to the part ~i+1~ is equal to the greatest common divisor of numbers ~a_i~ and ~a_{i+1}~ minus one. (Let us notice that in the case when the numbers are relatively prime, this is also true because we can prolong ~1-1 = 0~ cuts.) We leave the proof of this procedure for the reader to implement for practice. The greatest common divisor can be calculated using, for example, Euclid's algorithm because the naive method is too slow for large test data.

The COCI version of this task was significantly more difficult: the cuts could "jump over" vertical parts. In other words, the cuts didn't have to be continuous. What would the minimal possible number of cuts be in this situation?

We are looking for the number of different heights which we can make a cut on. Again, given the current vertical part which should be cut into ~T~ pieces, we are looking for the number of cuts which can be prolonged from one of the previous vertical parts. The heights we're interested in are ~\frac 1 T, \frac 2 T, \dots, \frac{T-1} T~.

When these fractions are irreducible, the denominators are divisors of ~T~. For each divisor ~d~, we come up with fractions ~\frac x d~, where ~(x, d)~ are relatively prime because the fraction is irreducible. Has the cut ~\frac x d~ appeared before? Yes, if it's equal to ~\frac{y}{T'}~ for a previous part numbered ~T'~, which means ~T'~ is a multiple of ~d~. If we've marked the appearance of all previous divisors ~d'~ of ~T'~ (using, for example, an array of ~0~ and ~1~), it is simple to check if ~d~ has appeared before.

The complete procedure goes like this: for each divisor ~d~ of the number ~T~ (we find the divisors with complexity ~\mathcal O(\sqrt T)~ we check whether we've used it before. In other words, if there are cuts ~\frac x d~. If not, we mark it as used and add all cuts ~\frac x d~ to the final solution, meaning that we are looking for the number of ~x~s smaller than ~d~ and relatively prime with ~d~, which is the Euler function of number ~d~. Its values can be calculated in advance using formulas for Euler's totient function.