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
The answer is 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)?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
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?
Is this algorithm O(n*log(n))?
Yes have a look at http://codeforces.me/blog/entry/8672 [354C — Vasya and Beautiful Arrays]
Yes , because N + N/2 + N/3 + N/4 ... + N/N = O(N log N)
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
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.
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)).
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.me/contest/364/problem/D
Try it out!
THx.
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