### PROBLEM LINK:

[Practice][111]

[Contest][222]

**Author:** Pavel Sheftelevich

**Tester:** Karan Aggarwal

**Editorialist:** Praveen Dhinwa

### 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

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

- 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.
- 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:

Author’s solution

Tester’s solution

[111]: http://www.codechef.com/problems/SQNUMBF

[222]: http://www.codechef.com/LTIME37/problems/SQNUMBF