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

Автор DryukAlex, 11 лет назад, По-русски

Здравствуйте. Мне пришла в голову одна задача, которую я не умею решать;) Даны N<=10^5 целых чисел от 1 до 10^9, и дано Q запросов, каждый из которых представляет целое число X, 1<=X<=10^9. Для каждого запроса нужно вывести количество чисел из списка, которые нацело делятся на X. Интересно, существует ли решение (онлайн/оффлайн) быстрее, чем за O(N) за запрос?.. Заранее спасибо;)

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

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

Совсем недавно была такая задача, но там числа до 10^5.

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

    Ага, значит, идея не нова;) А то, что всегда L=0 и R=N-1, задачу никак не упрощает?..

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

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

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

    Только хотел написать про то же. Еще добавлю, что факторизовать числа для нахождения их делителей лучше всего с помощью ρ-алгоритма Полларда.

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

      Спасибо большое, похоже на правду;) Единственное — не может ли в сумме делителей оказаться слишком много (скажем, 2*10^8) так, что они не влезут в память?

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

        vlad107 ниже предложил учитывать только те делители, которые есть в запросах. А на самом деле, делителей максимум O(sqrt(MAXVAL) + N) — у каждого числа может быть не более одного делителя больше корня, а всего различных делителей меньше корня — понятно, сколько.

        UPD. Насчет любых делителей больше корня я все-таки наврал. Это утверждение верно только для простых делителей.

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

    А как в онлайне быстро отвечать на запросы?

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

    10^8 чисел не очень приятно хешировать, тогда уже логичнее вначале захешировать все запросы, а потом учитывать только те делители, которые есть в запросах.

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

      Ага, красиво;) Получается, искать придется все равно все делители, но хешируются только нужные? Да, и кто-нибудь знает константу ρ-алгоритма Полларда?

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

        Я тестировал его на полупростых числах порядка 10^18 с умножением по модулю за логарифм и проверкой на простоту с помощью BigInteger.isProbablePrime(100). Отрабатывало меньше, чем за секунду на очень старом железе (Pentium 4 640, 3.2ГГц). Учитывая асимптотику , можете делать выводы.

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

          Однако... Даже если это старое железо делает всего миллион операций за "меньше, чем за секунду", получается константа 30;) Такое впечатление, что в моем случае быстрее будет идти по простым числам до корня...

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

            Я только что сравнил Полларда с перебором делителей на худших тестах против того и другого, т.е. полупростых числах порядка 10^9 с примерно равными делителями, при установке 1024 итераций до сброса начального значения Поллард все-таки работает чуть быстрее. А в целом — время работы все-таки слишком большое, поэтому стоит снижать ограничения до 10^7, чтобы заходило решето Эратосфена.

            Вот мой код.

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

              Хм, странно... Казалось бы — до корня из миллиарда 3-4 тысячи простых чисел, итого 300-400М взятий по модулю, секунд за 5 должно бы проходить... А если уменьшить ограничения до 10^8, простых чисел будет еще в 3 раза меньше, так что, наверное, это уже будет выгоднее, чем Поллард.

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

                В-общем, задача потеряла всю свою идейность и свелась к простому упихиванию факторизации 10^5 чисел :).

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

                  Увы;) На самом деле, изначально я придумал более сложную задачу — дано N различных чисел, нужно найти такое минимальное число X, что не более k чисел дают одинаковый остаток при делении на X. Но тут я уже не знаю, решается ли она даже за квадрат:(

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

                  В действительности достаточно пустить какое-нибудь решето до скажем N=10^5, затем перебрать все простые до K=10^9/N которых очень немного, и затем если число поделится найти остальные числа в разложении на простые. Т.е. Для Q=10^5 задача спокойно решается за пару секунд.

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

Вроде бы еще можно сохранить все различные числа из запросов, сжать их, а потом сделать sqrt-декомпозицию, хранить cnt[num][i] — количество чисел из блока num, делящихся на i-ый делитель из списка запросов. Если использовать хэш таблицу, то получается O(NsqrtN) на предпосчет и O(sqrtN) на запрос.

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

    Извините, не могли бы вы поподробнее объяснить, как делается предпросчет за O(NsqrtN)? У вас N чисел и Q запросов, для каждой пары вы делаете проверку для обновления cnt. Итого O(NQ). Извините, если неправильно понял вашу идею.

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

      Просто иду по массиву слева направо, и для текущего числа смотрю все его делители, если какой — то делитель встречался в запросах, то смотрю какой он сжатый и обновляю cnt. Псевдокод :

      for i 1..n
          for j 2..sqrt(a[i])
              if (a[i] % j == 0 && exist[j])
              {
                  cnt[block[i]][compr[j]]++;
      
                  if (a[i] / j != j && exist[a[i] / j])
                      cnt[block[i]][compr[a[i] / j]]++;
              }
      

      Ярые минусующие не любят корневую?

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

        А причем тут корневая? У вас это работает за n×sqrt (max_a)×map. У вас, кажется, наблюдается непонимание поставленной задачи.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

Извините, неправильно понял условие.