SM
Ну смысле за кол-во делителей
алгоритм вобщем работает за линию....а время восстановления крайне мала
Size: a a a
2020 July 19
Q
нужно хранить минимальный простой делитель для каждого из чисел...по ним возмжно будет восстановить общий ответ....время работы алгоритма O (n)
ну, я еще подумаю, может так и сделаю. Просто у меня там надо это будет делать 100500 раз, и возможно будет медленно каждый раз восстанавливать.
AF
алгоритм вобщем работает за линию....а время восстановления крайне мала
Алгоритм же работает за решето
SM
Quixiote
ну, я еще подумаю, может так и сделаю. Просто у меня там надо это будет делать 100500 раз, и возможно будет медленно каждый раз восстанавливать.
говорю же O(30) максимум
🎄T
Quixiote
ну, я еще подумаю, может так и сделаю. Просто у меня там надо это будет делать 100500 раз, и возможно будет медленно каждый раз восстанавливать.
Зачем 100500 раз одно и тоже делать?
SM
Алгоритм же работает за решето
решето работает за решето....это немного улучшеный вариант...так что работает быстрее
🎄T
алгоритм вобщем работает за линию....а время восстановления крайне мала
Ну восстановить можно за 8 операций
AF
решето работает за решето....это немного улучшеный вариант...так что работает быстрее
Это "линейное решето" с емакса да
AF
Хз насколько оно решето конечно
SM
Это "линейное решето" с емакса да
да...именно
Q
Хорошо, спасибо всем. Поизучаю еще это линейное решето на емаксе. Судя по всему, это то, что мне надо.
SM
Хз насколько оно решето конечно
типо O(n + n / 2 + n / 3 + n / 4 + ....) примерно O(2n)
A
типо O(n + n / 2 + n / 3 + n / 4 + ....) примерно O(2n)
Исходную задачу не смотрел но ничего что ряд расходится?
SM
Исходную задачу не смотрел но ничего что ряд расходится?
не думаю что при 1e5 этот будет проблемой....или я не прав?
P
не думаю что при 1e5 этот будет проблемой....или я не прав?
Не будет это никакой проблемой, коэффициенты не важны
P
О(N) и все
SM
Не будет это никакой проблемой, коэффициенты не важны
++
SM
О(N) и все
верно
A
не думаю что при 1e5 этот будет проблемой....или я не прав?
Посмотрел задачу. Вообще можно считать что константная сложность.
A
О(N) и все
И кстати это неверно