Максимальная сумма факторов чисел в данном диапазоне
Этим вопросом я занимался на какой-то онлайн-платформе судей.
Найти максимальную сумму множителей чисел от 1 до N.
Например, если N должно быть 11, ответ будет 18. Число с наибольшей суммой коэффициентов от 1 до 11 равно 10 (1 + 2 + 5 + 10).
Я реализовал относительно простое решение, которое выглядит как сито. Код на C ++ выглядит так:
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, я упрощаю вывод mx[N], Это решение кажется правильным. Тем не менее, он превышает ограничение по времени (1 с) для больших входов. Максимальное N — 1 000 000, но пользователь может запросить 1 000 000 различных значений N. Приведенный выше код является кодом предварительной обработки, который запускается один раз.
Сложность приведенного выше кода составляет N + N / 2 + N / 3 + … + 1, что, как я полагаю, касается N Log N. Как мне улучшить сложность этого кода?
Спасибо за помощь.
Решение
Ответ этой проблемы: Большое количество
Вы можете получить последовательность здесь: A002093
На самом деле, я проверил, что все чрезвычайно распространенные числа ниже 10 ^ 10 — это 41-гладкое число, а ниже 10 ^ 13 — 61-гладкое число.
N-гладкое число может разложить простые числа ниже 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), так что вы можете рассчитать функция делителя за O(log N + log X),
Я даю результат своего кода, например, я вычислил все 61-гладкие числа ниже 10 ^ 13, за 3,5 секунды, используя 1 ГБ памяти.
Другие решения
Других решений пока нет …