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 :

//Here MAX is the maximum element in the array
//freq[i] stores the frequency of i in the array
for i = MAX to 1 :
    cnt = 0
    j = i 
    while j <= MAX :
    if freq[j]>0 :
        cnt++ 
    j += i   
if cnt > 1 :
     ans = i    
     break

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.