You are not logged in. Please login at www.codechef.com to post your questions!

×

SQNUMBF - Editorial

PROBLEM LINK:

Practice
Contest

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

This question is marked "community wiki".

asked 25 Jun '16, 19:38

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

edited 25 Jun '16, 23:39

admin's gravatar image

0★admin ♦♦
19.8k350498541

2

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

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

10

Author's and Tester's solution links never work !! :(

EDIT: They are working now !! Thanks

link

answered 25 Jun '16, 22:50

torque's gravatar image

6★torque
4271111
accept rate: 17%

edited 26 Jun '16, 09:23

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

link

answered 25 Jun '16, 22:51

akulgoel96's gravatar image

3★akulgoel96
1086
accept rate: 12%

edited 25 Jun '16, 22:52

Nice method to reduce the complexity !!!

link

answered 25 Jun '16, 22:52

tihorsharma123's gravatar image

2★tihorsharma123
49718
accept rate: 15%

edited 25 Jun '16, 22:54

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.

link

answered 27 Jun '16, 00:38

vnvipinsingh's gravatar image

3★vnvipinsingh
213
accept rate: 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

link

answered 26 Jun '16, 00:31

tihorsharma123's gravatar image

2★tihorsharma123
49718
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) geek_geek4★

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

link

answered 26 Jun '16, 01:09

tihorsharma123's gravatar image

2★tihorsharma123
49718
accept rate: 15%

No. 1 sec ~ 10^7 Operations

(26 Jun '16, 05:45) geek_geek4★

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

(26 Jun '16, 10:01) sacheendra90445★

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.

link

answered 26 Jun '16, 04:07

likecs's gravatar image

6★likecs
3.7k2481
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) pranavarora6★

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

vnvipinsingh's gravatar image

3★vnvipinsingh
213
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★

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?

link

answered 26 Jun '16, 09:27

invincible42's gravatar image

4★invincible42
1
accept rate: 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.

link

answered 26 Jun '16, 14:57

kshitij_jain's gravatar image

3★kshitij_jain
663
accept rate: 0%

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

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

link

answered 26 Jun '16, 15:26

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

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

link

answered 28 Jun '16, 13:17

jyotsna_08's gravatar image

3★jyotsna_08
1
accept rate: 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).

link

answered 28 Jun '16, 22:59

sachinsahoo11's gravatar image

6★sachinsahoo11
353
accept rate: 0%

edited 28 Jun '16, 23:32

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.

link

answered 07 Jul '17, 19:44

master_bat's gravatar image

2★master_bat
111
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,852
×2,657
×639
×53
×9

question asked: 25 Jun '16, 19:38

question was seen: 5,611 times

last updated: 07 Jul '17, 19:44