×

# SQNUMBF - Editorial

Author: Pavel Sheftelevich
Tester: Karan Aggarwal
Editorialist: Praveen Dhinwa

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

• Find the gcd of all pairs $(a_i, a_j)$, if it is greater than one, output that.
• Otherwise for each number $a_i$, we can write it as $p^2 \cdot q$ where $p$ is a prime. Note that if $p \geq 10^6$, then $q \leq 10^6$. So, we iterate for each prime $p$ from $1$ to $10^6$ and check whether $p^2$ divides $a_i$. We will also iterate over all $q$ from $1 to 10^6$ and check whether $\frac{a_i}{q}$ will be a perfect square or not.

# 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
A number $x$ is square free if there does not exist a number $p$ s.t. $p^2$ divides $x$. Note that $p$ will be less than $sqrt(x)$. Note that if there exists such a $p$, we can find a prime number $p'$ dividing $x$ too by taking one of the prime divisors of $p$.

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.

1. $p \leq 10^6$ : We can check $x$ is divisible by $p^2$ or not. If yes, then $p$ is one of our possible answers.
2. $p \geq 10^6$ : $p \geq 10^6 \implies p^2 \geq 10^12 \implies q \leq 10^6$. So, $q \leq 10^6$. We can iterate over all $q$ for $1$ to $10^6$ and check whether $x$ is divisible by $q$ or not. If yes, we check whether $\frac{x}{q}$ is a perfect square or not. If yes, find the square root of $\frac{x}{q}$. It will be one of our possible answers.

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 COMPLEXITY

We 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".

2.5k53136170
accept rate: 20%

19.8k350498541

2

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

(25 Jun '16, 22:58) 4★

 10 Author's and Tester's solution links never work !! :( EDIT: They are working now !! Thanks answered 25 Jun '16, 22:50 6★torque 427●1●1●11 accept rate: 17%
 4 The practice and the contest problem link is redirected to LCOLLIS. Please fix. answered 25 Jun '16, 22:51 108●6 accept rate: 12%
 2 Nice method to reduce the complexity !!! answered 25 Jun '16, 22:52 497●1●8 accept rate: 15%
 2 kshitij_jain 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 21●3 accept rate: 0%
 0 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 497●1●8 accept rate: 15% 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)
 0 One general question : Does O(10^8) operations run in 2 second on codechef server? answered 26 Jun '16, 01:09 497●1●8 accept rate: 15% No. 1 sec ~ 10^7 Operations (26 Jun '16, 05:45) It works . if costly operations such as modulo or division are not used. (26 Jun '16, 10:01)
 0 Help Required !!. Solution Link 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 6★likecs 3.7k●23●80 accept rate: 9% My friend used the above-mentioned factorization and got AC. Here is the solution link: https://www.codechef.com/viewsolution/10606727 (26 Jun '16, 06:13)
 0 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 21●3 accept rate: 0% 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) snk9674★
 0 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 1 accept rate: 0%
 0 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 66●3 accept rate: 0%
 0 I am getting WA for third subtask. Can any one help? https://www.codechef.com/viewsolution/10614149 answered 26 Jun '16, 15:26 893●2●11●34 accept rate: 10%
 0 why is condition checked is iii<=x and 1e-6 added to t in setter solution? answered 28 Jun '16, 13:17 1 accept rate: 0%
 0 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 pre-compute 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 35●3 accept rate: 0%
 0 I think that I am the unluckiest creature on the earth. Can some pure soul created by GOD can help me in debugging my code. LINK P.S.:- I am getting WA in last task of last subtask and unable to upload image due to less reputation. answered 07 Jul '17, 19:44 11●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,639
×2,585
×631
×53
×9

question asked: 25 Jun '16, 19:38

question was seen: 5,551 times

last updated: 07 Jul '17, 19:44