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

№	Пользователь	Рейтинг
1	tourist	3757
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	171
2	awoo	165
3	adamant	164
4	TheScrasse	159
5	maroonrk	155
6	nor	154
7	-is-this-fft-	152
8	Petr	147
9	orz	146
10	pajenegod	145

Задача 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

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

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

→ Ответить

ilyakor

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

Zhukov_Dmitry

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

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

Просто возвращаем 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