There is n integer elements. Choose k elements then calculate their GCD, call result X.
What is maximal value of X?
k<=n<=3000, k<=100, elements in range 1..10^10.
Example:
3 2
120
36
100
Sample output
20
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | jiangly | 3631 |
| 4 | Kevin114514 | 3574 |
| 5 | maroonrk | 3521 |
| 6 | strapple | 3515 |
| 7 | Radewoosh | 3461 |
| 8 | tourist | 3428 |
| 9 | turmax | 3378 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 161 |
| 2 | adamant | 147 |
| 3 | Um_nik | 145 |
| 4 | Dominater069 | 142 |
| 5 | errorgorn | 140 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 30.05.2026 20:25:46 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
These constraints are in a very gray area, it really depends on the time limit. So depending on the limit you may or may not be able to:
Factor each number: Sieve of Eratosthenes + 3000 * (primes below 10 ^ 5) = 3000 * 10000; Generate divisors of each number in O(divisor_count). Divisor_count is at most 2300. Keep a frequency table for the divisors and just select the biggest one that's over k.
Just a first thought. It's a fragile solution, but it may very well work. Again, the constraints are too fuzzy. Will look for something cleaner and smarter though :).
If I correctly understood your solution it wouldn't work because the gcd can be a composite number instead of a prime.
I take in account all divisors, composite or not. The factoring into primes part is only so you can generate the divisors of a number quickly, instead of trying each number up to 10 ^ 5.
Thank you, I understood.
ez
gg easy FTFY