Q: Given an array of n integers, find the maximum value of GCD for all possible pairs.
Sample Test Case- 1 2 3 4 5 Output: 2
2<=n<=10^5
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.12.2024 12:15:21 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Take a look at this post.
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).
Please explain more. I don't understand anything.
for(int i=0;i<n;i++) { for(int j=1;j*j<=a[i];j++) { if(a[i]%j==0) { mark[j]++; mark[a[i]/j]++; } } } complexity is O(N*SQRT(MAX(A)))
I understood. Thank you.
If you are referring to the problem from the yesterday contest on CodeChef, I got AC in O(MaxA * log(MaxA)) by trying all possible GCDs and seeing if there are at least two numbers that divide it, same as mentioned in the post (link given in the first comment). However, it required some optimization to actually fit it into the TL (Like clearing the array of used digits in O(N) rather than in O(MaxA).). I wonder if there is a solution that doesn't depend on the values of numbers and is fast enough.
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
Oh really?! Obviously you got that. I'm no way trying to get the code. I had doubt that's it. Thanks a lot.Whatever, I'll figure it out.
Good luck then!