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

Автор rek, история, 8 лет назад, По-русски

Добрый день, Codeforces!

На днях столкнулся с такой вот задачей. Дано n различных целых положительных чисел (каждое из которых не превышает, скажем, 109). Необходимо найти наименьшее такое k, что все числа, взятые по модулю k, также окажутся различными.

Буду благодарен, если кто-нибудь предложит ненаивное решение (в частности, без явного подсчета всех попарных разностей) или хотя бы подскажет, в каком направлении копать.

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

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

Auto comment: topic has been translated by rek (original revision, translated revision, compare)

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

For each pair find a positive difference. Find all divisors of that difference — add them to global hash-table. Iterate numbers from 1 to infinity and check presence in hash-table. If it's not in hash-table, that's your k.

If you have pair 1 & 7, difference is 6, divisors are 1,2,3,6 (added to hash-table) — so the smallest k is 4. Keep adding divisors for other pairs and then find smallest k.

Complexity O(n * sqrt(m)), where n — number of pairs and m is 10^9 in your case.

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

    Thank you for your answer! Considering we have n numbers, we would get complexity, which is not much better than a naive solution, so I'm still looking for a better way to do this (if there's any).

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

Is there a constraint on k? Large k will always work

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

    Oh, thank you for this message, I didn't point before that k must be as small as possible. My fault.

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

Can you please post the link?

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Well, to tell the truth, there is no such competitive programming problem anywhere, my friend and I came up with the idea of it some days ago, and we have been looking for the solution for a few days, but we couldn't find anything similar either in archives or in Google, so I can't.