Как суммировать последовательность?
Как я могу суммировать следующую последовательность:
⌊n/1⌋ + ⌊n/2⌋ + ⌊n/3⌋ + ... + ⌊n/n⌋
Это просто O (n) решение на C ++:
#include <iostream>
int main()
{
int n;
std::cin>>n;
unsigned long long res=0;
for (int i=1;i<=n;i++)
{
res+= n/i;
}
std::cout<<res<<std::endl;
return 0;
}
Вы знаете лучшее решение, чем это? Я имею в виду O (1) или O (log (n)). Спасибо за ваше время 🙂 и решения
Редактировать:
Спасибо за все ваши ответы. Если кто-то хочет решение O (sqrt (n)):
Python:
import math
def seq_sum(n):
sqrtn = int(math.sqrt(n))
return sum(n // k for k in range(1, sqrtn + 1)) * 2 - sqrtn ** 2
n = int(input())
print(seq_sum(n))
C ++:
#include <iostream>
#include <cmath>
int main()
{
int n;
std::cin>>n;
int sqrtn = (int)(std::sqrt(n));
long long res2 = 0;
for (int i=1;i<=sqrtn;i++)
{
res2 +=2*(n/i);
}
res2 -= sqrtn*sqrtn;
std::cout<<res2<<std::endl;
return 0;
}
Решение
Это Сумматорная функция делителя Дирихле D (x). Используя следующую формулу (источник)
где
дает следующее O(sqrt(n)) псевдо-код (который является допустимым Python):
def seq_sum(n):
sqrtn = int(math.sqrt(n))
return sum(n // k for k in range(1, sqrtn + 1)) * 2 - sqrtn ** 2
Заметки:
-
//Оператор в Python является целым, то есть усечением, делением. math.sqrt()используется в качестве иллюстрации. Строго говоря, это должно использовать алгоритм целочисленного квадратного корня вместо математики с плавающей точкой.
Другие решения
Взято из статьи в Википедии о Сумматорная функция делителя,
где . Это должно обеспечить 
время решения.
РЕДАКТИРОВАТЬ: целочисленный квадратный корень проблема также может быть решена в квадратный корень или даже логарифмическое время — на случай, если это не очевидно.
Проект Polymath наметил алгоритм для вычисления этой функции за время O (n ^ (1/3 + o (1))), см. Раздел 2.1 на страницах 8-9:
http://arxiv.org/abs/1009.3956
Алгоритм включает разделение области на достаточно тонкие интервалы и оценки значение для каждого, где интервалы выбраны достаточно тонкими, чтобы оценка была точной при округлении до ближайшего целого числа. Таким образом, вы вычисляете до некоторого диапазона напрямую (они предлагают 100n ^ (1/3), но вы можете изменить это с некоторой осторожностью), а затем делаете все остальное в этих тонких срезах.
Увидеть запись OEIS для получения дополнительной информации об этой последовательности.
Edit: теперь я вижу, что Kerrek SB упоминает этот алгоритм в комментариях. Справедливости ради, однако, я добавил комментарий к OEIS 5 лет назад, так что я не чувствую себя плохо из-за публикации «его» ответа. 🙂
Я должен также упомянуть, что никакой алгоритм O (1) невозможен, так как ответ — около n log n и, следовательно, даже выписывая это занимает время> войти n.
Поделим все число {1, 2, 3, ..., n} на 2 группы: меньше или равно sqrt(n) и больше чем sqrt(n), Для первой группы мы можем вычислить сумму с помощью простой итерации. Для второй группы мы можем использовать следующее наблюдение: если a > sqrt(n), чем n / a < sqrt(n), Вот почему мы можем перебрать значение [n / i] = d (от 1 в sqrt(n)) и вычислить количество таких i тот [n / i] = d, Это можно найти в O(1) для фиксированной d используя тот факт, что [n / i] = d средства i * d <= n and i * (d + 1) > n, который дает [n / (d + 1)] < i <= [n / d],
Первая и вторая группы обрабатываются в O(sqrt(n)), который дает O(sqrt(n)) время в общей сложности.
Для больших nиспользуйте формулу:
где 
(
это трансцендентное число.)
Увидеть Постоянная Эйлера-Мачерони статья для получения дополнительной информации.
detector