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

Функция Ейлера
Автор lth, 15 лет назад, По-русски

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

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

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

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

→ Ответить
»
15 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
»
15 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Можно за

→ Ответить
»
15 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

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

→ Ответить
»
15 лет назад, скрыть # |
← 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) работает.

→ Ответить