SQNUMBF - Editorial

editorial
, , , ,
1

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.

  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:

Author’s solution
Tester’s solution
[111]: http://www.codechef.com/problems/SQNUMBF
[222]: http://www.codechef.com/LTIME37/problems/SQNUMBF

10 Likes
2

Author’s and Tester’s solution links never work !! :frowning:

EDIT: They are working now !! Thanks

5 Likes
3

The practice and the contest problem link is redirected to LCOLLIS. Please fix.

2 Likes
4

Nice method to reduce the complexity !!!

1 Like
5

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

1 Like
6

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

7

One general question : Does O(10^8) operations run in 2 second on codechef server?

8

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.

9

No.
1 sec ~ 10^7 Operations

10

You have done similar to editorial.
for(int meghana=1;meghana<=MAX;meghana++)
Boss, first who is meghana :stuck_out_tongue: ?

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

2 Likes
11

My friend used the above-mentioned factorization and got AC. Here is the solution link: https://www.codechef.com/viewsolution/10606727

12

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.

13

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?

14

It works . if costly operations such as modulo or division are not used.

15

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.

16

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.

17

I am getting WA for third subtask. Can any one help?

https://www.codechef.com/viewsolution/10614149

18

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.

1 Like
19

why is condition checked is iii<=x and 1e-6 added to t in setter solution?

20

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