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

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

Здравствуйте. Может кто знает как можно посчитать функцию Ейлера для всех i, 1 <= i <= n за время O(n)?

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

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

кстати задача с идущего контеста...

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

    Мне эта задача попалась на сайте spoj.pl

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

Могу посоветовать только http://e-maxx.ru/algo/prime_sieve_linear. Попробуй во время построения решета тащить еще функцию Эйлера. Если числа различаются на 1 простой множитель. пересчитать ее не составит труда.

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

    Спасибо, но такая сложность получит TLE. Поэтому мне нужна линия.

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

      А можно узнать, что за задача?

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

          Ну я ее сдавал подобным подходом, только считал для каждого числа его минимальный делитель, а на основании этой информации считал уже функцию Эйлера.

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

      Не верю в то, что там где пройдёт линия не пройдёт N * Log N. Логарифм по основанию E = 2.71...

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

    Кажется, асимптотика чуть лучше... (см. по этой же ссылке)

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

Оффтоп: не могли бы исправить Ейлера на Эйлера?

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

. Посчитаем сначала для всех чисел от 1 до n величину mindi — минимальный делитель числа (очевидно это простое число). Теперь будем считать величины phi(i) от 1 до n. Допустим мы нашли все phii до некоторого idx - 1 включительно и теперь хотим найти phi(idx). Тут два варианта либо простое mindidx входит в idx в степени ровно 1, либо в большей. Если оно входит в степени больше одного, тогда phi(idx) = phi(idx / mindidx) * (mindidx - 1) иначе phi(idx) = phi(idx / mindidx) * (mindidx). Все минимальные делители можно найти за O(n) крутым решетом Эратосфена с e-maxxа. Остальное тоже за O(n) работает.

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

    вроде, нахождение делителей за О(n) работает дольше, чем обычное решето

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

      Ну когда я в последний раз писал и правда получилось немного дольше. На 107 обычное решение работало 200, а за O(n) где-то 300. Но вроде автору хотелось решения за O(n) :-) А если нужно просто сдать задачу, то можно с хаками написать обычное решето и сдать

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

    По-моему, если MINDidx входит в idx в степени == 1, то phi(idx) = phi(idx / MINDidx) * (MINDidx — 1), иначе phi(idx) = phi(idx / MINDidx) * MINDidx.