Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 04.11.2010, 21:00
Новичок

Отправить личное сообщение для kobra Посмотреть профиль Найти все сообщения от kobra
 
Регистрация: 04.11.2010
Сообщений: 3

Поиск количества делителей чисел на заданом отрезке
http://acm.tju.edu.cn/toj/showp2861.html

Чесно говоря идей нет. Знаю как можна задачу решить за O(N*ln N), но в етом случае ни времени не хватит ни памяти. Мой алгоритм основан на формуле:
f(p_1^{a_1}*p_2^{a_2}*...*p_n^{a_n}) = (a_1+1)*(a_2+1)*...*(a_n+1)
но что делать с такими ограничениями я понятия не имею((
  #2  
Старый 04.11.2010, 21:37
гость

 
Сообщений: n/a

дома ты можешь вычислить табличку сумм f(x) на сетке размера скажем 100000. (зависит от предела на размер исходника). После этого таким образом тебе для каждого тест кейса нужно максимум вычислить две сумме на интервалах размера 100000.

А это можно сделать какой нибудь модифицией решета эратосфена.
  #3  
Старый 04.11.2010, 22:03
Новичок

Отправить личное сообщение для kobra Посмотреть профиль Найти все сообщения от kobra
 
Регистрация: 04.11.2010
Сообщений: 3

а нормального решения нет? без читерства?
  #4  
Старый 04.11.2010, 22:07
гость

 
Сообщений: n/a

Сообщение от kobra Посмотреть сообщение
а нормального решения нет? без читерства?
какое читерство??? это решение примут даже на финале icpc
  #5  
Старый 04.11.2010, 22:54
Новичок

Отправить личное сообщение для kobra Посмотреть профиль Найти все сообщения от kobra
 
Регистрация: 04.11.2010
Сообщений: 3

примут, но меня интерисует есть ли другой алгоритм, для которого не нужно считать сначала у себя на компе, а потом вставлять в код?
  #6  
Старый 06.11.2010, 01:22
гость

 
Сообщений: n/a

Есть такая мысль. Допустим надо посчитать f(1)+...+f(N). Оно просто равно сумме F(N) = \sum_{i=1}^N \lfloor N/i \rfloor. Т.к. число i делит ровно floor(N/i) чисел от 1 до N, ясно.

Как вычислить F(N) эффективно? По моему так: для i <= sqrt(N) считаем в лоб. Для i > sqrt(N) находим интервалы чисел [i1, i2] таких что N/i постоянно для i=[i1, i2]. Таких интервалов если не ошибаюсь тоже около O(sqrt(N)) штук. Ну и суммируем длину интервала на N/i в нем. Итого O(sqrt(N)) сложность алгоритма. И безо всякого прекалка.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
сортировка методом многофазного слияния огромного количества чисел esal Сортировка и поиск 2 26.10.2010 18:55
сумма делителей гость Математические алгоритмы 1 30.10.2009 00:25
Округление до количества значащих чисел spoilt_child Реализация, исходники, языки 5 17.12.2008 16:37
Поиск в массиве чисел всех интервалов с разнастью между элементами в еденицу. phprus Сортировка и поиск 2 15.01.2008 11:23
поиск арифм. послед. простых чисел Rulikkk Математические алгоритмы 1 29.01.2007 14:35