Максимальная сумма коэффициентов чисел в заданном диапазоне

Question

Это вопрос, который я делал на какой-то платформе онлайн-судей.

Найти максимальную сумму коэффициентов чисел от 1 до N.

Например, если N должны были быть 11, то ответ будет 18. Число с наибольшей суммой коэффициентов от 1 до 11, 10 (1 + 2 + 5 + 10).

Я реализовал относительно простое решение, которое выглядит как сито. Код в С ++, как показано ниже:

for (int i = 1; i <= 1000000; ++i { 
    for (int j = i; j <= 1000000; j += i) { 
     num[j] += i; 
    } 
    mx[i] = max(num[i], mx[i - 1]); 
} 

Всякий раз, когда запросы пользователей для некоторого N, я Simpy выход mx[N]. Это решение кажется правильным. Тем не менее, он превышает ограничение времени (1 с) для больших входов. Максимальное значение N равно 1 000 000, но пользователь может запросить 1000 000 различных значений N. Указанный код является кодом предварительной обработки, который запускается один раз.

Сложность вышеуказанного кода N + N/2 + N/3 + ... + 1, который, я полагаю, около N Log N. Как я могу улучшить сложность этого кода?

Благодарим за помощь.

Answer 1

Ответ этой проблемы: Highly Abundant Number
Вы можете получить последовательность здесь: A002093

На самом деле, я проверил, что все очень обильное число ниже 10^10 является 41-гладким числом, а ниже 10^13 - 61-гладкое число.
N-гладкое число может факторизовать ниже простые числа N.
Вы можете искать п-гладкое число, как этот алгоритм (. 47-ех гладкого число ниже 10^16):

vector<int> p = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 }; 
vector<long long> s = { 1 }; long long lim = 10000000000000000; 
for (int i = 0; i < p.size(); i++) { 
    vector<long long> w; 
    for (long long j : s) { 
     long long mul = j; 
     for (; mul <= lim; mul *= p[i]) w.push_back(mul); 
    } 
    s = w; 
} 

Вы можете факторизовать N- плавное число X в O(log N + log X), поэтому вы можете рассчитать divisor function за O(log N + log X).

Я даю результат моего кода, например, я вычислил все 61-гладкие числа ниже 10^13, за 3,5 секунды, используя 1 ГБ памяти.