Задача 25 ЕГЭ под олимпиадным углом: как найти число с ровно K делителями быстрее перебора?
В задачах на делители часто просят найти числа с ровно заданным количеством делителей в диапазоне. Прямой перебор каждого числа с подсчётом делителей за O(sqrt x) на больших диапазонах не успевает. Можно ли посчитать количество делителей для всех чисел диапазона разом, чтобы было быстрее?
2 ответа
Да, если диапазон [1, n] помещается в память — считай число делителей сразу для всех чисел «решетом делителей» за O(n log n), а не каждое отдельно за O(sqrt x).
Идея: для каждого делителя d пройдись по всем его кратным d, 2d, 3d, ... и прибавь 1 к их счётчику делителей. Суммарно это n/1 + n/2 + n/3 + ... = O(n log n) (гармонический ряд).
// число делителей для всех i в [1, n] за O(n log n)
vector<int> divisor_count(int n) {
vector<int> d(n + 1, 0);
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j += i)
d[j]++;
return d;
}
Потом ответ на «сколько чисел в [L, R] имеют ровно K делителей» — один проход: for (i = L; i <= R; i++) if (d[i] == K) ans++;. Итог — O(n log n) предподсчёт + O(R-L) на запрос, вместо O((R-L)·sqrt(R)) при наивном подходе.
Если же диапазон огромен (до 10^12) и массив не влезает — придётся факторизовать каждое число за O(sqrt x) и считать d(x) = ∏(a_i + 1), тут решето не поможет.
Полезный факт для ускорения single-number версии: число делителей нечётно тогда и только тогда, когда число — полный квадрат (делители разбиваются на пары d и x/d, кроме случая d = x/d). Это иногда позволяет сразу отсечь кандидатов. И ещё — если ищешь числа с малым числом делителей (например, ровно 2 — это простые, ровно 3 — это p^2), часто проще породить их конструктивно из простых, чем перебирать все числа подряд.