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

How to solve this hard problem about set?
Автор kien_coi_1997, 10 лет назад, По-английски

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
Теги set
  • Проголосовать: нравится
  • +43
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится +30 Проголосовать: не нравится

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

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

    If I correctly understood your solution it wouldn't work because the gcd can be a composite number instead of a prime.

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

      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.

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

    Thank you, I understood.

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

ez

→ Ответить