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. In the HONI version, the candy is from the interval ~[1, 10^6]~, whereas in the COCI version it is from the interval ~[1, 10^8]~. Also, ~N~ in HONI would not exceed ~1000~, whereas in COCI it would not exceed ~100~.

We will interpret the task in the following way: for an array of numbers of length ~N~, for each ~x~ from ~1~ to ~N~, we need to determine the minimal number with which we need to divide every array item so that we are left with a group of exactly ~x~ equal numbers in the array or we need to determine that such number doesn't exist. If we mark the greatest number in the array with ~V~, it is clear that all the solutions belong in the interval ~[1, V+1]~.

Our first solution is now formed, its complexity being ~\mathcal O(NV)~. For each ~x~ from the interval ~[1, V+1]~, we can determine how many numbers give a certain quotient when performing division with ~x~ with the help of a counter in an array, which we update accordingly.

For a solution which performs for ~100\%~ of points, we need to come up with a faster way to calculate how many numbers give a certain quotient when performing division with the number ~x~.

The following can be noticed:

• the numbers which give the quotient ~0~ when performing (integer) division with ~x~ are from the interval ~[0, x-1]~
• the numbers which give the quotient ~1~ when performing (integer) division with ~x~ are from the interval ~[x, 2x-1]~
• in general, the numbers which give the quotient ~k~ when performing (integer) division with ~x~ are from the interval ~[kx, (k+1)x-1]~

If we can build a structure which can quickly give an answer to the query How many numbers in the array are from the interval ~[a, b]~ then we can determine how many numbers give the quotient ~k~ when performing division with ~x~. Given the fact that the array numbers are not greater than ~10^6~, the structure can be a simple array ~A[]~ where ~A[t]~ stands for the number of elements in the original array smaller than ~t~. Now we can calculate the number of numbers in the original array from the interval ~[a, b]~ with the formula ~A[b]-A[a-1]~.

The greatest quotient ~k~ which can happen for a certain ~x~ is ~\frac V x~. This is why we need to make ~\frac V x + 1~ queries to determine how many numbers there are which give the quotient ~0, 1, 2, \dots, \frac V x~ when performing division with ~x~. Because we have to test all numbers from ~1~ to ~V+1~ for a certain ~x~, we have ~V + V \times \left(\frac 1 1 + \frac 1 2 + \dots + \frac 1 {V+1}\right)~ queries in total. Therefore, the complexity of this algorithm is ~\mathcal O(V \log V)~.

The COCI version of this task had different limitations: ~N \le 100~, ~V \le 10^8~. This version required a different approach.

For each number ~K~ in the array, we can observe the following array: ~[\frac K 1], [\frac K 2], \dots, [\frac K {K+1}]~, where ~[x]~ marks the floor of value ~x~. We can notice that this array is going to consist of blocks of consecutive equal values. We will call number ~i~ important if ~[\frac K i]~ is different from ~[\frac K {i-1}]~.

Now we can use an algorithm similar to the initial solution of complexity ~\mathcal O(NV)~, except now we don't need to test every ~x~ from ~1~ to ~V+1~. Instead, it is sufficient to check only the important numbers for each element we have in the array because the not important number ~x~ will have all quotients equal to those of some important number.

Now the complexity is ~\mathcal O(N \times \text{the total number of important numbers} \times \log N)~. It can be shown that for a number ~K~, there exist ~\sqrt K~ different important numbers at most, so the total complexity is ~\mathcal O(N^2 \sqrt V \log N)~.