Problem Link: http://www.codechef.com/problems/BYTES4 Difficulty : Medium Hard Strategy : GCD,Sieve Explanation : Here we have to find the maximum GCD of all the pairs possible. The most trivial method is to evaluate the GCD of each possible pair and store the maximum but this would take O(n^2) time complexity but it would lead to TLE. We can make a algorithm with better complexity using the fact that the values of the integers has an upperbound . We will use a sieve like approach to solve this problem . Now first lets solve another problem , given a value X we have to tell whether a pair has a GCD equal to X . This can be done by checking that how many elements in the array are multiple of X. If the number of such multiples is greater than 1 , then X will be a GCD of some pair. Now to solve this problem , we can check all the values of X from 1000000 to 1 whether they can be a GCD of some pair. Pseudocode for the problem :
Now , the complexity of this algorithm is given by the divisor summatory function and this case it will be D(MAX) and the time complexity of this function is till an open problem known as the Dirichlet divisor problem. But for the given time limit this solution will pass. asked 05 Feb '14, 12:06

"given a value X we have to tell whether a pair has a GCD equal to X . This can be done by checking that how many elements in the array are multiple of X. If the number of such multiples is greater than 1 , then X will be a GCD of some pair" This is incorrect consider say, array is [6,18], X=3, gcd of only pair is 6 and not 3. answered 18 Jul '17, 13:34

No it's not incorrect, this is because here we are iterating from MAX(largest element of array) to 1, so in your example X = 6 will come before X = 3, hence the solution is correct answered 18 Jul '17, 15:35

Ya that i accept :) But i was saying for a general case.. you cam't say this. answered 18 Jul '17, 21:39

I am not able to understand.Please, can you explain once in the more elaborate manner? answered 18 Jul '17, 22:07

Please Help, I am unable to understand why my code gives Wrong Answer! Codehere answered 25 Aug '18, 17:32

@behalgitanshu Pls see if the indentation of the code is correct. I edited it as it was unclear earlier
Should it not be cnt += freq[j]? What happens if the input it T=5, and arr[] = {1, 1, 1, 10, 10}. Here pairwise maximum GCD is 10, but since when i = 10, the cnt will be 1, and hence will proceed to the point where i = 1 and give output at 1. Is there anything I'm missing here?
@destination_i you are correct, it should be cnt+=freq[j]
what if the range of values would have been large like 10^9?
Nice explaination. (y)