Блог пользователя 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 Проголосовать: не нравится

        http://www.spoj.pl/problems/GCDEX/

        → Ответить
        • »
          »
          »
          »
          »
          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.

    → Ответить