Greatest GCD between some numbers

11 лет назад, # ^ |

a[i] < 100,000

→ Ответить

11 лет назад, # ^ |

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?

→ Ответить

flashmt

11 лет назад, # |

← 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)

→ Ответить

11 лет назад, # ^ |

Is this algorithm O(n*log(n))?

→ Ответить

Dixtosa

11 лет назад, # ^ |

Yes have a look at http://mirror.codeforces.com/blog/entry/8672 [354C — Vasya and Beautiful Arrays]

→ Ответить

kingofnumbers

11 лет назад, # ^ |

Yes , because N + N/2 + N/3 + N/4 ... + N/N = O(N log N)

→ Ответить

alexyz

11 лет назад, # ^ |

← Rev. 5 →

-8

My comment is wrong.

→ Ответить

11 лет назад, # ^ |

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)

→ Ответить

alexyz

11 лет назад, # ^ |

I'm sorry. "Sieve of Eratosthenes" algorithm use only prime numbers, which are spreaded as O (log (n))

→ Ответить

11 лет назад, # ^ |

do you mean n / log(n) ?

→ Ответить

11 лет назад, # ^ |

Thanks! It is really n*logn

→ Ответить

11 лет назад, # |

← 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.

→ Ответить

11 лет назад, # ^ |

← 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)).

→ Ответить

11 лет назад, # ^ |

← 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?

→ Ответить

caustique

11 лет назад, # ^ |

You can apply your idea in that problem http://mirror.codeforces.com/contest/364/problem/D

Try it out!

→ Ответить

11 лет назад, # ^ |

THx.

→ Ответить

11 лет назад, # ^ |

← 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))

→ Ответить

11 лет назад, # ^ |

Yeah, you're right. I've noticed that. Thx.

→ Ответить