1
1

Добрый день!

Возникла еще одна задача на алгоритм. Есть функция f(n). Она вычисляет наибольший делитель числа n, такой, что он не делится на 2. Имеется отрезок [a, b]. Известно, что a и b сверху ограничены числом N. Требуется описать алгоритм как посчитать вот такую сумму f(a) + f(a + 1) + f(a + 2) + · · · + f(b − 1) + f(b). Желательно, чтобы он работал как можно быстрее (как функция от N).

Подскажите, пожалуйста.

задан 11 Сен 14:35

изменен 11 Сен 14:49

2

Числа разбить на группы, в которых равны степени двойки в каноническом разложении. Этих групп не более $%\left\lceil{\log_2N}\right\rceil$%. Сумма в каждой группе вычисляется за $%O(1)$% - это арифметическая прогрессия. Итого $%O(\log_2N)$%.
Конечно, это не алгоритм, а общая идея, так что и вам кое-что на подумать перепадет.

(11 Сен 17:49) spades
2

Тут я приношу извинения. Сумма прогрессии требует одного сложения, одного вычитания и одного умножения, которые не мгновенны, а $%\log N, \,\, \log N, \,\, \log N \cdot \log\log N$% соответственно. То есть асимптотика алгоритма будет $%O(\log^2N\cdot \log \log N)$%

(11 Сен 19:45) spades
10|600 символов нужно символов осталось
1

Алгоритмическое решение.
Пусть $%S$% - искомая сумма. Решение основано на формуле $%S=S_0-\frac12 S_1-\frac14 S_2-\ldots$%,
где $%S_0$% - сумма всех чисел от $%a$% до $%b$%, $%S_1$% - сумма чисел, делящихся на $%2$%, $%S_2$% - делящихся на $%4$% и т.д. Все это приводит к простенькому алгоритму:

$%result = S(a,b)$%
$%\operatorname{while} \,\, (b>a):$%
$%\quad a \leftarrow \left\lceil{ a/2 }\right\rceil, \,\, b \leftarrow \left\lfloor{b/2}\right\rfloor $%
$%\quad result \leftarrow result - S(a,b)$%

$%\operatorname{if} \, \,(b=0):$%
$%\quad \operatorname{return} \,\, result $%

// для небольших интервалов ($%b-a<\log_2b$%) не всё вычли

$%\operatorname{while} \,\, (b \mod 2 =0):$%
$%\quad b \leftarrow {b/2} $%
$%\quad result \leftarrow result -b$%

$%\operatorname{return} \,\, result $%

$%\operatorname{END}$%
Здесь $%S(a,b)$% -сумма всех чисел от $%a$% до $%b$% включительно.

P.S. Хотел, чтобы уважаемый топикстартер попытался пройти от идеи, высказанной в комментарии, до практической реализации. На мой взгляд, это полезный скилл. Но раз уж выложили решение, то и мне не жалко.
Это решение можно улучшить, убрав из тела цикла умножение - на каждом шаге вычитаемая сумма уменьшается практически в четыре раза с небольшой добавкой. Эту добавку можно посчитать только сложением/вычитанием, получая итоговое время $%O(\log^2 N)$%. Но в решении не стал загромождать техническими деталями, при желании можно проделать это самостоятельно

ссылка

отвечен 12 Сен 0:43

изменен 12 Сен 1:27

10|600 символов нужно символов осталось
1

Конкретный и весьма быстрый способ вычисления таков. Положим F(n)=f(1)+...+f(n), где f(k) есть наибольший нечётный делитель k. Достаточно уметь быстро находить F, чтобы далее вычислить разность F(b)-F(a-1).

Нечётные числа, не превосходящие n, в сумме дают 1+3+...+(2k-1)=k^2, где k=[(n+1)/2]. Далее учитываются чётные, что равносильно нахождению F от [n/2]. Отсюда ясно, что F(n)=[(n+1)/2]^2+F([n/2]).

По этой схеме, легко найти F(n) даже вручную для конкретных значений n. Например, F(100)=50^2+F(50), F(50)=25^2+F(25), F(25)=13^2+F(12), и так далее. То есть F(100)=50^2+25^2+13^2+6^2+3^2+2^2+1^2=2500+625+169+36+9+4+1=3344.

ссылка

отвечен 11 Сен 21:26

@falcao: спасибо!

(12 Сен 17:51) ТриКота
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×86

задан
11 Сен 14:35

показан
97 раз

обновлен
12 Сен 17:51

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru