Problem link : contest practice Difficulty : Easy Prerequisites : Greedy, Prime factorisation Problem : You are given an array of integers, anytime you can pick two numbers from it and divide them both by some common factor of them. Your goal is to find the minimal possible product of the numbers of an array after performing a number of such operations. Explanation : Let's decompose each number into the product of primes, that is, let's find it's factorisation. We know that A_{i} is not greater than 10^{9}. So, if there is a prime factor that is greater than, say 40000 (virtually, greater than the square root of 10^{9}), it will appear only once in the decomposition. So, each prime number greater than 40000 will appear in the final product of the array elements no more than once. Each number from the array may or may not have this prime factor in its prime decomposition but if it has, this prime factor will appear only once in this number's decomposition. So, for each prime divisor greater than 40000 if it appears in the even number of the array elements, then it is possible to split the numbers that have this divisor into pairs and to get rid of it completely. If it appears in the odd number of the array elements, then we can pair up all but one numbers that have this factor in their prime decomposition. So, it will appear once in the final product in the array elements. For the rest of prime numbers, that is, those that are smaller than 40000, we can solve the problem separately, and the solution here is a greedy one:
In order to pick two maximal numbers and to change them we can use the STL priority queue. But there is also an alternative to store something like the amount of every list's number occurences in the array, like Amount[X] the number of X's in the list. That makes the implementation easier for Pascal coders.
This question is marked "community wiki".
asked 27 Apr '14, 14:00

Here is the proof that I did while setting the problem, just for the part why the greedy step is correct. It might wave a little away from the editorial's context; any suggestions are welcome. First of all we can treat each prime separately. So prime factorize the numbers and treat the prime powers individually. For powers of a prime P, we take the largest two, divide by P and insert it back to the list. Proof that this greedy step is correct : Consider an optimal solution, which is a list of pairs of indices, such that if ith element of the list is (a_i, b_i) that means the ith operation was to divide A[a_i] and A[b_i] by P. It is easy to see that division by higher powers of P can be reduced to multiple elements in the list (division by P^2 can be converted to two divisions by P). Let l1 and l2 be the indices of the largest two powers of P. We have to show that there is an optimal list which has (l1,l2) in it. Hence by contradiction there is always an optimal solution that has (l1,l2) in it. answered 27 Apr '14, 14:26

Can the test cases be made public? So that we can debug our code. answered 27 Apr '14, 14:53

I did the same thing,and divided the numbers by their HCF repeatedly,and I too believe this should be the solution...... answered 01 May '14, 00:02

can someone tell me what is wrong with my code ?. i was submitting it for the smaller part but was getting WA on the last case ..plz tell me what is wrong answered 27 Apr '14, 14:11

http://www.codechef.com/viewsolution/3795105 Why is my submission giving wa? answered 27 Apr '14, 14:19
