FCUBE - editorial

PROBLEM LINK:

Practice
Contest

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:

  1. Use a map (or a dictionary in some languages) to keep count of the factors
  2. For each A_i, find all prime factors less than \sqrt[3]{A_i} and increment their count. Also divide them from A_i.
  3. 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}.
  4. 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.
  5. For all A_i's which are not processed in steps 3 and 4, increment the count by 1
  6. 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).

AUTHOR’S, TESTER’S and Editorialist’s SOLUTIONS:

setter
tester
editorialist

Problems to Practice

3 Likes

What’s wrong with my approach?

I generated all the primes upto 10^6 and stored it in an array.
For each number Ai, I found its product of prime form and stored the power of each prime number in a hash table. Then for each element in the hash table, i found its modulus with 3, so remainder is either 1 or 2 or 0. Now, if remainder is 1, I multiplied that prime twice with result, for mod 2, I multiplied the prime once. Then I multiplied all the numbers input (Ai) with result. This should give the first cube (and it does for all my test cases). But I am getting WA for all subtasks. I think my approach is correct at least for the first sub task.

My code

For step 2, we need to count all the prime factors of A_i less than cube root of A_i. For that the order will be around 10^6, so the order of step 2 will be O(n*10^6). That will be a major component in the order of the solution.

Please correct me if I am wrong.

I did the same thing, still some error. See this question for explanation

http://discuss.codechef.com/questions/65152/wa-in-fcube-getting-015-points

1 Like

why my code gives a runtime error sigsegv…??

I checked some top solutions against the following test case and nobody passed…

http://pastebin.com/7DY3JtQ1

1 Like

Weak test cases for FCUBE

The test cases for the problem are weak. For the worst case accepted solution are showing TLE on ideone.

Solution 1 Accepted link

Solution 2 Accepted Link

I checked only for 2 submissions. Please help if the test case is wrong.

http://discuss.codechef.com/questions/65170/weak-test-cases-for-fcube

I don’t know why but I just find all primes number less than 5 * 10^3 and get AC (after several submits :smiley: ). Here’s my AC code (Java).

http://www.codechef.com/viewsolution/6336344

Hello admin and others ,

Can anyone tell me why my code is giving WA for subtask3. I have been trying to get the test cases from the last 4 hours but still it is not getting Accepted. Please check

http://www.codechef.com/viewsolution/6336326

Why am I getting TLE?
http://www.codechef.com/viewsolution/7267905

Practice link is not working.

Prime factors. There are less than 10^6 primes \le 10^6.

I’m guessing most numbers in the input have small prime factors, which makes a code like mine significantly faster.

I was doing similar thing, but it was TLE.

Yup the prime factors are less than 10^6 (78498 to be exact). But the main component should still be O(n*78498).

Perhaps the test cases were weak, your solution is showing TLE for the worst case. xRVOuj - Online C++0x Compiler & Debugging Tool - Ideone.com . Please correct me is the test case is wrong.

1 Like

yes, it seems like test cases are slight weak :frowning:

@abcdexter24 even for sub task 1?

Yeah, that’s what I was saying. That the tests are weak. I don’t think it’s possible to get AC on worst case tests without some HEAVY optimisation.

what if S is a prime number more than 10^6? I think you are missing that condition.

2 Likes

@dpraveen: can you add stronger tests to practice?