PROBLEM LINK:
Author: Sergey Kulik
Tester: Roman Furko
Editorialist: Balajiganapathi Senthilnathan
DIFFICULTY:
Medium
PREREQUISITES:
Prime numbers, GCD, divisors
PROBLEM:
Given a number S = A_1 * A_2 * A_3...A_n such that 1 <= A_i <= 10^{18}, find the first multiple of S that is a cube.
QUICK EXPLANATION:
In a cube each prime factor’s exponent is a multiple of 3. For each A_i, count the number of times a prime divisor of A_i \le \sqrt[3]{A_i} occurs and remove all the powers of this divisor from A_i. Now, we can have at most 2 prime factors still remaining in A_i.
-
A_i = p * q
To find the factors for a particular A_i, we take gcd of A_i and all other number A_j. If this gcd g \gt 1 and g \ne A_i, then g is a factor of A_i. So, we count g and \frac{A_i}{g}. -
A_i = p^2
If we don’t get a factor this way, we can observe that A_i is a square of a prime. If so, we count this prime twice. If we still can’t factorize A_i, we just count A_i because if there are two prime factors of A_i, their exponent will be equal in S.
Now that we have got count of the exponent of all the prime factors, we loop through them and if their exponent is not a multiple of 3, we increase the exponent till it is a multiple of 3. Finally, we multiply all the factors raised to their exponents to get the final answer.
EXPLANATION:
First let us see how a cube looks like. Say we have a number N and it can factorized as N = p_1^{x_1}*p_2^{x_2}*p_3^{x_3}...p_m^{x_m}, N^3 will be p_1^{3x_1}*p_2^{3x_2}*p_3^{3x_3}...p_m^{3x_m}. Observe that each prime factor’s exponent is a multiple of 3. How does that help us? Suppose S can be factorized as \prod_{i = 1}^{m}p_i^{x_i} , to make it a cube we have to increase each of the exponents till it is a multiple of 3. We can’t get a cube which is a multiple of S less than that.
Now we can’t calculate the prime factorization easily except in the first subtask. We need to come up with a cleverer way. What if we factorize as much as we can? We can’t run a loop till \sqrt{A_i}, but we can factorize till \sqrt[3]{A_i}. So, after removing all prime factors less than \sqrt[3]{A_i}, we will have only prime factors which are greater than \sqrt[3]{A_i}. How many such prime factors can be there?
Claim: For a number X, there can only be up to 2 prime factors which are greater than \sqrt[3]{X}.
Proof: Suppose there are 3 prime factors p_1, p_2 and p_3 greater than cube root of X. i.e. we have p_1 \gt \sqrt[3]{X}, p_2 > \sqrt[3]{X} and p_3 > \sqrt[3]{X}. Multiplying the 3 we get p_1 * p_2 * p_3 \gt X, which implies X \gt X - a contradiction.
Note that you will have to pre-calculate all the primes \le 10^6 and only check with these to pass within the time limit.
Now that we have established that, let us see how much more prime factors we can extract. If you think about this, there are 3 possible cases:
Case 1: A_i = p^2
Here A_i is a perfect square. We can easily check for each A_i whether it is a perfect square and increment the count of p accordingly.
Case 2: A_i = p_1 * p_2 and there exists A_j = p_1 * p_3
We have to extract p_1 and p_2. Since p_1 is common for A_i and A_j while p_2 \ne p_3, we conclude that gcd(A_i, A_j) = p_1. Once we get p_1, we can also get p_2. So, for each A_i, we loop through all other numbers and take g = gcd(A_i, A_j). If g is non-trivial (g \gt 1 and A_i \ne g), we will have this case and we can increment the count for g (= p_1) and \frac{A_i}{g} (= p_2). Note that this will also work if A_j = p_1 i.e. A_j itself is a prime number.
Case 3: A_i = p_1 * p_2 and there is no other A_j such that A_j = p_1 * p_3 or A_j = p_2 * p_4
In this case we can just consider A_i as a single factor. Because p_1 and p_2 always go together, we can count them as a single factor. If there is another number equal to A_i, we just increment the count accordingly.
Final solution:
- Use a map (or a dictionary in some languages) to keep count of the factors
- For each A_i, find all prime factors less than \sqrt[3]{A_i} and increment their count. Also divide them from A_i.
- For each A_i, loop through all other numbers A_j and take their gcd g. If g \gt 1 and g \ne A_i, then increment counts for g and \frac{A_i}{g}.
- For all A_i which were not processed in step 3, find if it is a perfect square. You can do it using binary search or using your language’s square root function (but you have to be careful of precision issues). If it is a perfect square, then increment the count of its square root by 2.
- For all A_i's which are not processed in steps 3 and 4, increment the count by 1
- Finally, loop through all the factors counted, and increment their count till they are a multiple of 3. Now multiply each factor count times. Make sure mod is taken into account.
Complexity
Suppose d is the number of factors of S. Step 2 will take \mathcal{O}(1) since the number of prime numbers less than 10^6 is constant. For step 3, we are looping through n other numbers and taking gcd. So it will take \mathcal{O}(n). Step 4 and 5 we can safely ignore since they are not dependent on n or d. Since we are doing steps 2 to 5 for all A_i, the total complexity will be \mathcal{O}(n^2). Step 6 takes \mathcal{O}(d) steps. So overall complexity is \mathcal{O}(n^2 + d).