PROBLEM LINK:Author: Pavel Sheftelevich DIFFICULTY:medium PREREQUISITES:number theory, prime representation of numbers PROBLEM:You are given a number $X$ which is denoted by product of $n$ numbers $a_1, a_2, \dots, a_n$. A number is called square free number if there does not exist a number greater than one whose square divides the number perfectly. You are guaranteed that $X$ is not square free. You have to find any $p \leq 10^{18}$ whose square divides $X$. QUICK EXPLANATION
EXPLANATION:We have to find a number $p$ such that $p^2$ divides $X = a_1 \cdot a_2 \cdot \dots, a_n$. Let us first check whether the numbers $a_i$ are square free or not. If they are not square free, we will try to find one $p$ s.t. $p^2$ divides $a_i$. This $p$ will be one of our answers as $p^2$ will also divide $X$. Checking whether a number $x$ is square free or not So, the simplest solution will be to iterate over all primes $p \leq sqrt(x)$ and check whether $p^2$ divides $x$ or not. Time complexity of this algorithm will be around $\mathcal{O}(10^9)$ for $x = 10^18$, which won't pass for large subtask. Can we find a better solution? Let us represent number $x$ as $p^2 \cdot q$ s.t. $p$ is a prime. Notice that when $p$ is small, we can just check $x$ by dividing it by $p^2$. When it gets bigger, we notice that $q$ will be smaller, and we can check whether $x/q$ is a perfect square or not. Let us describe this again more accurately.
Now, assume that we find that all the numbers $a_1, a_2, \dots, a_n$ all are square free. Can it still happen that their product is square free. Yes, it can happen. If a number $p$ exists which divides some $a_i, a_j, j \neq i$, then the product $X$ won't be square free and $p$ will be one of possible answers. So, for each pair of numbers $a_i, a_j$, we have to check whether these exists a number other than 1 which divides both of them? In other words, we want to know whether these two numbers are coprime or not. For that, we just find their $gcd(a_i, a_j)$ and check whether it is equal to 1 or not. TIME COMPLEXITYWe iterate over all $a_i, a_j$ and check their gcds. It will take $\mathcal{O}(n^2 log(max(a_i))$ time. Time complexity of checking a number $a_i$ is square free is $\mathcal{O}(a_i^{\frac{1}{3}})$. So, total time in checking whether all $a_i$'s are square free or not will be $\mathcal{O}(10^6 \cdot n)$ in the worst case, as $a_i$ can go up to $10^{18}$. Total time complexity will be $\mathcal{O}((n^2 \, log(max(a_i) \, + 10^6 \cdot n)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 25 Jun '16, 19:38

Author's and Tester's solution links never work !! :( EDIT: They are working now !! Thanks answered 25 Jun '16, 22:50

The practice and the contest problem link is redirected to LCOLLIS. Please fix. answered 25 Jun '16, 22:51

Nice method to reduce the complexity !!! answered 25 Jun '16, 22:52

one more possibility exist that the A[i] can be composite number but A[i] != prime * prime. A[i] = prime1 * prime2 where prime1 != prime2. answered 27 Jun '16, 00:38

I implemented the exact thing in editorial but sill getting TLE in last two cases Here is my submission : https://www.codechef.com/viewsolution/10610721 Can anyone help me out why this is happening? Thanks in advance answered 26 Jun '16, 00:31
4
You have done similar to editorial. for(int meghana=1;meghana<=MAX;meghana++) Boss, first who is meghana :P ? Istead of going from 1 to max You can check only for the prime number from 1 to MAX which you have already generated. This is the only difference between your code and my code. My Code in python : https://www.codechef.com/viewsolution/10600162
(26 Jun '16, 05:51)

Help Required !!. I have a different approach for the question. The first part is same as the editorial i.e. If GCD of all numbers is not equal to one, the answer is GCD. For the second part for finding the prime factorization or any prime number less than ${10}^{6}$ dividing ${a}*{i}$, I am using Pollard rho brent factorization. I know that it completely factorises the given number in O(${n}^{1/4}$ $log{n}$). So for ever ${a}*{i}$, I factorise it completely using the above technique. For even faster results, I return the smallest prime factor of every number less than ${10}^{6}$ in O(1) (after an initial sieve). Also, while factorization, if any prime number has a count greater than 1, I break the process there only, thus saving the time for further process. I easily pass the constraints for last subtask, but don't know why it is giving TLE for lower constraints with ${a}_{i}$ <= ${10}^{12}$. If anyone, could point out a mistake in my algorithm or code, it would be really helpful. answered 26 Jun '16, 04:07
My friend used the abovementioned factorization and got AC. Here is the solution link: https://www.codechef.com/viewsolution/10606727
(26 Jun '16, 06:13)

Editorialist: Praveen Dhinwa I have doubt, please tell me where i am wrong Let in one of the test case, N = 4, A[1] = b * b where b > 10^8 and b is prime, A[2] = k, A[3] = l, A[4] = m, Where all are prime and all are different and all are > 10^8 {b, k, l, m}, X = A[1] * A[2] * A[3] * A[4], Let find gcd of all pair, that will be one for all pair Now if we do this for all A[i]’s We run the loop till p <= 10^6 to find out A[i] is divisible by p^2 But we will not find any p such that p^2 divide A[i] We run the loop till q <= 10^6 Check whether A[i] is divisible by q If yes then check A[i]/q is perfect square or not And we fail to find any q such that q^2 divide A[i] But the solution exist which is b.
link
This answer is marked "community wiki".
answered 26 Jun '16, 08:20
q starts from 1,and for q=1, A[1]/q will be b^2 which is a perfect square. So, the answer is b in this case.
(26 Jun '16, 12:54)

Won't the number of operations be atleast 5 * 10^8 in the worst case as t <= 5? Then how will it run under 2 seconds? answered 26 Jun '16, 09:27

I did something similar but got WA, can someone tell me what is the flaw in this approach ? For every $a_i$, iterate over all primes <= $10^6$ and store the count of primes dividing the $a_i$ in a map. Now we are left with number >= $10^6$ such that it is not divisible by any prime which is less than $10^6$ . Now there exist only two possibilities, that either this number is prime or is it $prime^2$, so I check with Miller Rabin algorithm whether the number is prime or not. If it is prime, I store it in the map else I output the square root of the number. We check if there was no output in the previous step, we iterate over all primes and their frequency and see if their frequency >=2. answered 26 Jun '16, 14:57

I am getting WA for third subtask. Can any one help? answered 26 Jun '16, 15:26

why is condition checked is iii<=x and 1e6 added to t in setter solution? answered 28 Jun '16, 13:17

invincible42 : No, we only need to check divisibility by the prime numbers and the number of prime numbers less than 10^6 is ~78,000 . So, we can precompute all the prime numbers upto 10^6 (using sieve) then if we see the algo the complexity will only be of the order of O(t * n * (no. of primes < 10^6)) i.e. O(5 * 100 * 78,000)~O(10^7). answered 28 Jun '16, 22:59

The trick was simple, yet not that intuitive. A nice problem and a good editorial. :)