PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Animesh Fatehpuria
Editorialist: Pawel Kacprzak
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Number theory, primes, fundamental theorem of arithmetic
PROBLEM:
For a given array A[1..N] of N integers, the goal is to use the minimal number of operations of multiplying some of these integers by any prime numbers, in such a way that after all these multiplications are performed, then for each two possible different elements of the array A[i] and A[j], the value of A[i] \cdot A[j] is a square number.
QUICK EXPLANATION:
Use fundamental theorem of arithmetic to observe that a number K is a square if and only if each prime number than occurs in the unique factorization of K occurs there even number of times. Use this fact to determine the minimum number of operations needed to compute the final result.
EXPLANATION:
First, notice that K is a square number if all of its prime divisors divides K even number of times. This is the crucial fact to come up with the solution of the problem.
For now let’s assume that all input numbers are primes, which corresponds to what we have in the first and the second subtask. As we will see, this assumptions helps a lot with approaching the problem. Later, we will get rid of this limitation, and the resulting solution will be the exact method used in other subtasks.
Let’s pick any element of the array. Let’s assume it is A[i] and that A[i] = p, where p is some prime number. The question is what is the minimum number of times p has to be multiplied by some primes in order to be sure that when it is multiplied with any other number (remember, we have primes only) from the array, the result is a square number?
Since p is prime, it has only one prime in its factorization and it is exactly p. Moreover, it occurs there odd number of times, so in order to make A[i] \cdot A[j] a square number, where A[j] \neq p, then at least A[i] or A[j] has to be multiplied at least once by p, to make the factor of p appearing even number of times in the product. This fact applies to all A[j] \neq p, so in order to make all products A[i] \cdot A[j] to be square numbers for all A[j] \neq p, then either A[i] has to be multiplied at least once by p or each such A[j] has to be multiplied by p.
Here comes the next crucial observation. If we consider S to be a set of all elements of array A with the value p, then first of all, each element of S should be multiplied by the same primes, because if one method minimizes the number of multiplications needed for one element with value p then it can be applied to all elements with value p and it will be optimal for all of them. Thus, all elements in S will be multiplied by the same primes, so their final value will be the same. This implies that a product of any two elements of S after the multiplications are done is a square number. Moreover, since we noticed that in order to make the product of A[i] \cdot A[j], where A[i] \in S and A[j] \not\in S a square number, we either have to multiply A[i] once by p or all A[j] once by p, so if we consider all elements of S at once, then either we multiply each of them by p once or multiply each element not in S by p also once in order to make p a factor occurring even number of times in any of products we consider.
Based on the above observation we can came up with the following approach. Let’s consider all unique primes in the input. Moreover, let c_p be the number of times that p occurs in the input. Then in order to make all products in which exactly one of the elements has initial value p a square numbers, we have to use \min(c_p, N - c_p) multiplications by p.
Subtasks 1 and 2
Solutions to the first two subtasks are the exact implementation of the method described above.
Subtasks 3 and 4
Solutions to the last two subtask are follow ups to the method described above. Just to recall, in these subtasks there can be numbers in the input array that are not prime. However, it turns out that the solution for in this case is very similar to the one described above.
Let’s consider a prime number p occurring odd number of times as a factor of exactly c_p elements of the input array. Then in order to fix the all the products of pairs of elements of A, where exactly one of elements of each such pair has p occurring odd number of times as its factor, we have to multiply either all such c_p elements by p or all N - c_p other elements by p, and the minimum value of these two leads to the optimal solution. So the only thing to do is to first compute the list of all primes below 10^6, which can be done using for example the Sieve of Eratosthenes, and then for each of these primes, accumulate the number of input elements that are divisible by such a prime an odd number of times. For implementation details please refer especially to setter’s solution listed below which exactly matches the method used here.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.
