### affix's blog

By affix, 8 years ago, We've got n nonnegative numbers (a[i]) . We want to find the pair with maximum gcd. For example if we have:

2 4 5 15

gcd(2,4)=2

gcd(2,5)=1

gcd(2,15)=1

gcd(4,5)=1

gcd(4,15)=1

gcd(5,15)=5

n<100,000 and a[i]<100,000

I have an O(n*sqrt(n)) algorithm is there more efficient algorithm like O(n*logn) or O(n)? gcd, Comments (27)
 » What's the limitation for the numbers itself?Or we can suppose that a[i] = O(n)?Otherwise, you can factor all numbers and do something with it. In that case assympotics will include sqrt(max(a[i])) and probably it will be better.
•  » » a[i] < 100,000
•  » » I can optimize my algorithm to O(max_a[i] * sqrt(max_a[i]) ) but it is not fast enough. I heard there is O (max_a[i] * log(max_a[i])) algorithm! do you have any idea?
•  » » i did factor and get the gcd by this Mark all divisors of each element, in O(sqrt(n)). Then find maximum element of mark array that is marked more than twice, in O(n). but i really also need to know for which such pair is it the max wrt this solution how do i calculate which pair it is ?? Please help and reply asap
•  » » » You can maintain an auxiliary "vector of array" for that
•  » » » » but how should i know which pair to count ?
•  » » » » » Trying week of code. Lol.
 » 8 years ago, # | ← Rev. 2 →   for d = 1..10^5 for i = 1..10^5/d sumCnt += cnt[i * d] if (sumCnt >= 2) ans = max(ans, d) 
•  » » Is this algorithm O(n*log(n))?
•  » » » Yes have a look at http://codeforces.com/blog/entry/8672 [354C — Vasya and Beautiful Arrays]
•  » » » Yes , because N + N/2 + N/3 + N/4 ... + N/N = O(N log N)
•  » » » 8 years ago, # ^ | ← Rev. 5 →   My comment is wrong.
•  » » » » You are wrong. Not all implementations of "sieve of Eratosthenes" require N Log Log N time. Algorithm above is N log N because N + N/2 + N/3 + N/4 ... + N/N = O(N log N)
•  » » » » » I'm sorry. "Sieve of Eratosthenes" algorithm use only prime numbers, which are spreaded as O (log (n))
•  » » » » » » do you mean n / log(n) ?
•  » » Thanks! It is really n*logn
•  » » bro could u explain what is sumcnt and cnt
 » 8 years ago, # | ← Rev. 2 →   I am thinking of a way a little bit strange to solve this problem. You just randomly pick up two numbers and calculate the gcd. Run it 100000 times. Your possibility to get the right answer is very close to 1. Try it out.
•  » » 8 years ago, # ^ | ← Rev. 3 →   It is not true. Test case 2 4 1 1 1 .. 1 1 1 (99998 times one). Probatility to choose first and second numbers is 2 / (n * (n — 1)).
•  » » » 8 years ago, # ^ | ← Rev. 2 →   Every time the possibility I didn't choose 2 4 is p, then p = (1 — 2/(n * (n — 1))). So in the end, the possibility that I didn't come up with the right answer is p ^ 100000. I think is close to 0. Is that it?
•  » » » » You can apply your idea in that problem http://codeforces.com/contest/364/problem/DTry it out!
•  » » » » » THx.
•  » » » » 8 years ago, # ^ | ← Rev. 3 →   Not so close. Lets k = n * (n — 1) / 2. p = 1 — 1/k. it's well known equation 1 / e ~ (1 — 1 / k)^k for big k. e = 2.712. ln(e) = 1. So probability to not choose first two numbers is about (1/e)^(2 / (n — 1)) ~ 1 / (1 + 2/(n — 1))
•  » » » » » Yeah, you're right. I've noticed that. Thx.
•  » » » OK, sorry for my idea without test. In fact, p^100000 is about 0.9998....So in this problem, n' scale is 100000, this method didn't work out. However, when n is about 400 or smaller, 100000 times can almost gives a right answer.
•  » » » » When N is so small we could check all possible pairs. I think your idea doesn't work for these kinds of problems.
 » This question is close with HackerRank WoC 34 #2 (https://www.hackerrank.com/contests/w34/challenges/maximum-gcd-and-sum), please don't answer comments like written today and from "fake" accounts till end of competition. However, there is answer in comments... Good luck