Блог пользователя ScienceGuy

Maximum of GCD of N numbers
Автор ScienceGuy, история, 7 лет назад, По-английски

What is the efficient algorithm to find the maximum Greatest Common Divisor of N numbers? Input: First line contains N (2<=N<=10^5). Next line contains N numbers, each of them more than 1 and less than 10^5, output: Output the largest GCD of any pair of numbers.

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

https://www.hackerrank.com/contests/w34/challenges/maximum-gcd-and-sum

Come on dude. Cant wait 10 hours more?

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Assign v, v[x] = 1 if there was a number divisible by x. Go with i through the array. Find all divisors of a[i], for each divisor x, if v[x] = 1 update maximum with x. Solution O(N^1.5).

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

You can iterate over all possible gcds and for each check if there exist two or more numbers divisable by it (and if there are, choose two largest).

If you do it in way like this:

for (int gcd = 1; gcd < m; gcd++) {

for (int i = gcd; i < m; i += gcd) {

...

it will work in O(m log m) because m/1 + m/2 + m/3 + ... + 1/m = m * (1/1 + 1/2 + 1/3 + ... + 1/m) = m * O(log m) = O(m log m)

→ Ответить