Помогите придумать алгоритм (задача о делителях)

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Задача J с Huge Easy Contest II на uva.onlinejudge.org (текст задачи в оригинале на английском).

Вольный перевод:

Стив играет с числами. Он выбирает произвольное число N и находит наибольшее положительное число, не превосходящее N, имеющее наибольшее число делителей.

По мере увеличения N, Стиву все сложнее избежать ошибок при подсчете делителей, поэтому он просит вас написать программу. Вы утверждаете, что найти делители числа - легкая задача, поэтому вы легко сможете решить исходную задачу Стива.

Входные данные

В первой строке дается количество тестов T (T ≤ 50000). В следующих T строках записано единственное число N (1 ≤ N ≤ 10⁶), соответствующее данному тесту.

Выходные данные

Каждая из T строк должна содержать единственное число - ответ на задачу Стива.

SAMPLE INPUT

SAMPLE OUTPUT

Подскажите, пожалуйста, идею, как решить эту задачу.

Комментарии (15)

Написать комментарий?

freopen

14 лет назад, # |

Если построить решето Эратосфена и хранить в нем дополнительно хотя бы один делитель, можно за время порядка log(n) найти разложение числа на простые. После чего несложно подсчитать количество делителей для всех входных данных сразу.

→ Ответить

ilyakor

Казалось бы, можно для каждого числа до 10^6 посчитать число делителей - это будет недолго (например, динамикой: если x = p^α · y, и y не делится на p, то число делителей x равно числу делителей y, умноженному на α + 1). А дальше совсем просто - например, посчитать массив частичных максимумов и искать бинпоиском ответ на запрос.

Zhukov_Dmitry

14 лет назад, # ^ |

Зачем бинпоиск, если у нас есть массив частичных максимумов?

Просто возвращаем N-ый элемент этого массива.

Ну да, если мы вместе с максимумом храним, где он достигается (нам ведь нужно не количество делителей, а число с таким количеством).

nulpatrol

Есть ведь формула для подсчета количества делителей. Вот только для каждого числа использовать эту формулу...

Можете пояснить про формулу?

yeputons

Насколько понимаю, через разложение на простые множители (x = p₁^a₁· p₂^a₂..., d(n) = (a₁ + 1)·(a₂ + 1)·...)

VladBelous

+15

Мне кажется, тут чрезмерно усложняют решение. Не нужно никаких разложений на простые.
Достаточно сделать наблюдение, что число i является делителем всех чисел {i, 2i, 3i, ... m*i}, m*i<=N.
Следовательно, меняем i от 1 до 10^6, а j от i до 10^6 с шагом i, и внутри этого двойного цикла увеличиваем divisors[j] на 1.
Оценка (MlogM), где M у нас и есть 10^6.
Чтобы отвечать на запросы за O(1), проще всего сначала посчитать (за линейное время) частичные максимумы.

Решето Эратосфена

ballon

← Rev. 2 →

А как решать аналогичную задачу когда N<=10^18 ?
Тимус: 1748. Самое сложное число

Vasya.V

Перебор по невозрастающим степеням разложения числа на простые множители проходит.

Scalar

Точно так же - сгенерировать максимумы перебором, учитывая, что нам не нужны большие простые числа (не больше 47 вполне хватит).

Хм, а можно подробнее про вариант Timus 1748?

Написал решение использующее препроцессинг A[i] = "наименьшее n, кол-во делителей которого равно i". Тогда наибольшее i будет чуть больше 10^5. Делал перебор по невозрастающим степеням.

Решение проходит за ~0.7сек, однако, я смотрю, у большинства решение за 15-30мс и используется гораздо меньше памяти.

Подскажите пару идей?

Попробуй посмотреть на ответы для больших чисел и на их разложение на множители.

Пусть у нас есть приоритетная очередь кандидатов в максимумы (меньшие числа имеют больший приоритет). Достаем очередное число a с вершины. Если у него количество делителей не больше чем у предыдущего максимума, то выкидываем его. Иначе это очередной максимум. Для него кладем в очередь числа a*2, a*3, a*5... (простые числа до 47), если еще не происходит переполнение. Вначале в очередь кладем 1. В таком виде перебор проходит довольно быстро - 31 мс.

Блог пользователя agul