PROBLEM LINK:Setter Kirill Gulin DIFFICULTY:EASY PREREQUISITES:Sieve of Erastothenes, Binary Search PROBLEM:Given an array $A$ of $N$ integers, we have to maximize the GCD of all elements of the array. To do that, you can select any array element $A_i$ which is divisible by any number ${d}^{2}$, divide it by ${d}^{2}$ and multiply any other array element by $d$. QUICK EXPLANATION:Key to AC Realize that manipulation of powers of one prime is independent of powers of other primes. Perceiving that this question is more about manipulating prime and their powers rather than some complex mathematics theorem was important. Make a list of primes, and smallest prime divisors of all numbers in range using sieve. Now, for each prime $p_i$, keep a note of how many array elements are divisible by it, and what is the power of $p_i$ in their prime factorization form. Now whats left is finding what power of this prime can we maximum achieve in final answer using above operations  we can use BSH (Binary Search Heuristics) for this. Repeat for all primes and get an AC :). EXPLANATION:This editorial is divided into $2$ sections. The first section will highlight on the preprocessing required, and the second section will feature how to calculate answers using Binary Search Heuristics (BSH). Note that, I assume you all realize that, using operation of same number (i.e. dividing the same element by ${d}^{2}$ and increasing it by $d$) is useless. It will just reduce the prime power of that prime, which we might want to maximize for GCD. 1. Preprocessing It seems kind of obvious that we might need factorization of elements. Also, usually such problems do involve manipulation of prime numbers. Hence the first step is to use sieve of erastothenes to precalculate
The observation to make is that manipulation of exponents of prime factors of $A_i$ are independent. We can choose a prime $d$ every time for our operation so that only the chosen prime gets affected. If this doesnt ring a bell, you can refer to tab below. This is important as it helps in realizing that, increasing GCD prime by prime is the way to go. It gives an intuition that  "Ok, initialize GCD=1 for now. Lets pick a prime. Let me see what is the maximum possible power of it I can get for GCD of array using above operations. Multiply answer by it. Lets repeat this until we get answer." What is the next thing we need if we are to do such manipulations? We'd need the prime numbers and their exponents for all elements of array. I specifically liked the tester's method of storing it (to use it later) and I think it can use some credit :) .Its in tab below for reference. 2. Binary Search Heuristics I hope that the intuition so far, especially that of manipulating prime by prime, is clear to you. Now, for each prime, we will Binary Search on the highest possible power achievable (of that prime) in the final GCD. It is actually quite simple. Lets say we have to check if a power $k$ is achievable for some prime $p$. How do we do it? Recall that using our operation, we can reduce the power of $p$ in some $A_i$ by $2$ and increase power in another $A_i$ by $1$. In a way, its like "Sacrifice $2$ powers of some $A_i$ for $1$ power in another element." Since we aim to calculate Gcd, our aim is to maximize the minimum power $p$. Now, we have to check if we can make exponent of $p$ equal to $k$ in GCD. Hence, it makes sense to calculate how much "excess exponent" of $p$ can we take from "rich $A_i$", and how much exponent do we need to "poor $A_i$" to make exponent of $p$ equal to $k$ in GCD. It can be elegantly done if you have preprocessed the exponents and primes like tester did. The tester used a vector Now, things are quite simple. If we have gained sufficient exponent from "Rich $A_i$" to give to "Poor $A_i$", then a power of at least $k$ is achievable in the final GCD. We check for the highest power achievable using binary search (proof in tab below). The code to implement this is given below :) SOLUTION:The solutions are also pasted in tab below for you guys to see. Please refer to them in case links dont work. @admin may need time to link solutions up :) $Time$ $Complexity=$ $O((K+N)logN)$ where $K$ is number of primes in given constraints of $A_i$ CHEF VIJJU'S CORNER :D1. Is this problem solvable if we raise constraint of $A_i$ to $1 \le A_i \le {10}^{9}$? 2. Usually, many problems using GCD need knowledge of Mobius Function, Euler Totient functions etc. There is a very good blog describing them here 3. Linear Sieve deserves a mention here. :) 4. Prove that you can get an AC by this approach For above approach, solve the following
Credits for this question to  @codebreaker123
This question is marked "community wiki".
asked 21 Jul '18, 22:13
showing 5 of 7
show all

another possible solution:
final solution: ans * g. This can be extended for A[i] <= 10^9 (by considering primes upto $1000$). let me know if I am wrong. answered 23 Jul '18, 13:40
1
https://www.codechef.com/viewsolution/19318590 using setter solution but only considering primes until 100. :)
(23 Jul '18, 14:18)
Good job. :)
I doubt that. The reason is that your assumption  Currently, $A_i \le {10}^{6}$, so say if $p>100$. If we say that $A_i$ is divisible by $p$ even after dividing by ${p}^{2}$, then $A_i \ge {p}^{3} \implies A_i > {100}^{3}$ (as $p>100$) $\implies A_i >{10}^{6}$. Since $A_i \le {10}^{6}$, this means $p<100$ This will not hold for ${10}^{9}$
(23 Jul '18, 14:47)
2
for A[i]<=10^9 we will need to consider primes till 1000. :) in general for any n, we need to consider primes till n^1/3. sorry for not explicitly mentioning that.
(23 Jul '18, 16:12)
Yesss. Exactly! Infact, if you consider primes upto ${10}^{6}$, I feel we can solve it for $A_i<{10}^{18}$ as well. Very decent effort from your side :)
(23 Jul '18, 16:57)
an excellent observation :)
(23 Jul '18, 20:59)
Thank you. :)
(23 Jul '18, 21:05)
1
@codebreaker123 Very nice observation. And thanks @vijju123 for the awesome editorial :)
(25 Jul '18, 02:17)
I found this method also; shake out the initial gcd and then only primes below the cuberoot of the limit can support the 2for1 deal.
(15 Aug '18, 05:11)
showing 5 of 8
show all

i think the complexity should be k.N.logN, please correct if i am wrong. answered 23 Jul '18, 10:35
The time complexity is derived from tester's solution. He first factorises all array elements in $O(NLogN)$, and then for every prime he applied binary search $O(kLogH)$ where $H$ is the highest power of that prime.
(23 Jul '18, 14:55)
1
inside the while loop of binary search, there is also a for loop which can go upto n, so i think it should be O(k.n.logH)
(23 Jul '18, 16:15)
Can you please pinpoint the location? Cannot get it.
(23 Jul '18, 21:02)
@vijju123 Bro, see these lines> for (int k : id[x]) if (k >= h) now += ((k  h) >> 1); // sum, that we can use for (int k : id[x]) if (k < h) now = (h  k); // sum, that we need in idx[x] where x is prime, holds exponent of x in every Ai so i guess overall complexity will be O(NLogN+k.(summation of number of element id[x] for each prime)*logH)... if i am right, can u prove that this solution will not give TLE ?
(26 Jul '18, 08:43)
please someONe reply?
(27 Jul '18, 20:24)
1
I had answered this already in an ans on next page. I say, lets try to get an upper bound on number of iterations. It cannot be $O(N*K)$ as that'd mean every array element $A_i$ is divisible by each of $k$ primes  not possible based on my previous arguments. At max, how many iterations can it go then? Each element $A_i$ is divisible by $<log_2N$ primes. So worst case calculated by me was select $logN$ smallest primes such that their product is $<{10}^{6}$. Let it be $X$. Make an array with $N1$ elements $X$ and one element $1$. That gave $O(NLogN)$ complexity.
(27 Jul '18, 20:40)
showing 5 of 7
show all

The proof to my solution: Let g be the gcd of A[i]s. Now the gcd of A[i]/g to will be 1. (Pretty straight forward to see. Consider gcd be x. If gcd > 1, it contradicts that gcd of A[i] is g as every A[i] will then be divisible by g*x) Now consider any number d> 100. In the best case, d can divide (n1) numbers and maximum power of d on any of the nimber is 2. So, consider that d^2 divides (n1) numbers. Now we have 2 cases:
You can also see that the numbers cant be made divisible by d by using the tester can function for md=1. You need 1 more divisor, how ever you can get int((21)/2) * (n1) divisors = 0. I rest my case. answered 24 Jul '18, 08:44

Difference between (Line 135) ( answered 23 Jul '18, 00:53
Infinite loop? XD
(23 Jul '18, 00:59)
1
Yes. xDDDD . P.S.  Realised one more advantage of xD  bypass limit of 10 character. xD
(23 Jul '18, 01:01)

The tester solution is showing runtime error in my IDE. answered 23 Jul '18, 14:39
1
Thats because of their assert statements. Codechef IDE adds extra character at end of file. One way around is, to remove the Their assertions are done to make sure there are no trailing spaces in input etc. which might cause NZEC error for some java and/or python users. OR replace their assert statements with simple cin/cout or scanf/printf :)
(23 Jul '18, 14:57)
1
Ohh!!..Okayy, actually there was a mistake in my binary search..I was trying to find that...A great editorial though @vijju123...
(23 Jul '18, 15:01)
Thank you :)
(23 Jul '18, 15:29)

What am I doing wrong?? I had the same logic but its giving me wrong answer. answered 23 Jul '18, 19:42

Your solution is really too detailed，Thank you :) answered 23 Jul '18, 20:18

If anyone can tell me why code is giving me a run error it'll be great :) https://www.codechef.com/viewsolution/19341290 answered 26 Jul '18, 00:33

Very nice,detailed and easy to get editorial.Really loved it. answered 27 Jul '18, 09:52

help me.. i am getting tle answered 27 Jul '18, 20:40
Convert recursive to iterative one.
(28 Jul '18, 13:47)
@vijju123 got Ac, my finding smallest factor for each number using seive was slow regarding max A[i]=10^6.. *O(A[i].log[Ai]) ~~ 2 * 10^8 ==tle so optimised my code little bit, got ac
(29 Jul '18, 21:44)
now my code is fastest among all java submission for this problem.. thanks for replying
(29 Jul '18, 21:45)

Can it be done in this manner: Calculate total number of times a prime number appears in the factorization of every array elements like in example 3,15,15,27,1024 total number of 3's are six and 2's are ten. Now simply multiply all the prime numbers with count greater than or equal to number of elements+1. Please tell me if I am wrong? answered 14 Aug '18, 23:49

https://www.codechef.com/viewsolution/20550090 Can some one help me understand, why is my solution giving wrong answer. answered 07 Oct '18, 22:15

problem links are pointing to different problem bro. Nice work btw
Thanks for telling that. The time in hand to prepare editorials was lesser than a drop of sand xD
Done. xDDD
Thank you @aryanc403.I will check other editorials as well.
Why does the condition in the binary search use (r  l > 1) instead of (r > l)?
There are many variants of binary search. Nothing special in that condition.
Its that, if rl=1, then mid will always be equal to $l$. Might result in infinite loop. So setter kept r= Max Possible Value+1 (i.e, our answer is between $[l,r)$ instead of $[l,r]$).
Nicely Explained! Keep it up bro :)