### 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)?

• +7

 » 8 years ago, # |   -7 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.
•  » » 8 years ago, # ^ |   0 a[i] < 100,000
•  » » 8 years ago, # ^ |   0 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?
•  » » 4 years ago, # ^ |   0 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
•  » » » 4 years ago, # ^ |   0 You can maintain an auxiliary "vector of array" for that
•  » » » » 4 years ago, # ^ |   0 but how should i know which pair to count ?
•  » » » » » 4 years ago, # ^ |   0 Trying week of code. Lol.
 » 8 years ago, # | ← Rev. 2 →   +15 for d = 1..10^5 for i = 1..10^5/d sumCnt += cnt[i * d] if (sumCnt >= 2) ans = max(ans, d) 
•  » » 8 years ago, # ^ |   0 Is this algorithm O(n*log(n))?
•  » » » 8 years ago, # ^ |   0 Yes have a look at http://codeforces.com/blog/entry/8672 [354C — Vasya and Beautiful Arrays]
•  » » » 8 years ago, # ^ |   +1 Yes , because N + N/2 + N/3 + N/4 ... + N/N = O(N log N)
•  » » » 8 years ago, # ^ | ← Rev. 5 →   -8 My comment is wrong.
•  » » » » 8 years ago, # ^ |   0 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)
•  » » » » » 8 years ago, # ^ |   0 I'm sorry. "Sieve of Eratosthenes" algorithm use only prime numbers, which are spreaded as O (log (n))
•  » » » » » » 8 years ago, # ^ |   0 do you mean n / log(n) ?
•  » » 8 years ago, # ^ |   +1 Thanks! It is really n*logn
•  » » 7 weeks ago, # ^ |   0 bro could u explain what is sumcnt and cnt
 » 8 years ago, # | ← Rev. 2 →   0 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 →   0 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 →   0 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?
•  » » » » 8 years ago, # ^ |   0 You can apply your idea in that problem http://codeforces.com/contest/364/problem/DTry it out!
•  » » » » » 8 years ago, # ^ |   0 THx.
•  » » » » 8 years ago, # ^ | ← Rev. 3 →   0 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))
•  » » » » » 8 years ago, # ^ |   0 Yeah, you're right. I've noticed that. Thx.
•  » » » 8 years ago, # ^ |   0 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.
•  » » » » 8 years ago, # ^ |   0 When N is so small we could check all possible pairs. I think your idea doesn't work for these kinds of problems.
 » 4 years ago, # |   +17 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