Разложение на множители и делители

Разложение до корня

vector<pair<long long, int>> factorize(long long n) {
    vector<pair<long long, int>> result;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p) continue;
        int power = 0;
        while (n % p == 0) { n /= p; power++; }
        result.push_back({p, power});
    }
    if (n > 1) result.push_back({n, 1});   // остаток тоже простой
    return result;
}

Две вещи, на которых спотыкаются.

Условие цикла проверяет текущий остаток, а не исходное число. По мере деления n уменьшается, и корень уменьшается вместе с ним — цикл заканчивается раньше.

Остаток в конце. Если после цикла n > 1, это простое число, большее корня от исходного. Забыть про него — значит потерять самый крупный множитель. У числа $2 \cdot 999999937$ все делители до корня маленькие, а весь ответ сидит именно в остатке.

Проверять делимость на составные числа не вредно: к моменту, когда цикл дойдёт до четвёрки, все двойки уже поделены, и остаток на четыре не разделится.

Делители

Все делители числа перебираются до корня парами: если $d$ делит $n$, то и $n/d$ делит.

vector<long long> divisors(long long n) {
    vector<long long> result;
    for (long long d = 1; d * d <= n; d++) {
        if (n % d) continue;
        result.push_back(d);
        if (d != n / d) result.push_back(n / d);   // точный квадрат — не дублируем
    }
    return result;
}

Проверка d != n / d нужна ровно для точных квадратов: у 36 делитель 6 нашёлся бы дважды.

Сколько делителей бывает

Из разложения $n = p_1^{a_1} \cdot \ldots \cdot p_k^{a_k}$ число делителей считается формулой:

$$d(n) = (a_1 + 1)(a_2 + 1)\cdots(a_k + 1)$$

Каждый делитель — это выбор степени для каждого простого, независимо от остальных.

Величина эта растёт очень медленно. У чисел до $10^9$ максимум — 1344 делителя, до $10^{18}$ — 103 680. То есть делителей всегда мало, и хранить их списком не страшно.

Практический вывод: если в задаче надо что-то сделать «для каждого делителя», это дёшево. Дорого — найти сами делители, и вот тут помогает решето с минимальным простым.

Сумма делителей

Та же логика даёт и сумму:

$$\sigma(n) = \prod_{i} \left(1 + p_i + p_i^2 + \ldots + p_i^{a_i}\right)$$

Каждая скобка — геометрическая прогрессия, и её можно свернуть в $\frac{p^{a+1} - 1}{p - 1}$.

Делители всех чисел сразу

Если нужны делители каждого числа до $n$, перебирать каждое до корня — это $O(n \sqrt{n})$. Есть способ лучше: пройтись по каждому возможному делителю и отметить его кратные.

vector<vector<int>> divisorsOf(n + 1);
for (int d = 1; d <= n; d++)
    for (int m = d; m <= n; m += d)
        divisorsOf[m].push_back(d);

Работы здесь $\sum_{d} n/d \approx n \ln n$ — то самое гармоническое число. Для $n = 10^6$ это около 14 миллионов операций.

Тот же приём в упрощённом виде считает, например, количество делителей у каждого числа: вместо списка достаточно счётчика.

Взаимная простота и функция Эйлера

Сколько чисел от 1 до $n$ взаимно просты с $n$? Ответ даёт функция Эйлера:

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

Произведение берётся по различным простым делителям. Формула — прямое следствие включения-исключения: из всех чисел выбрасываем кратные каждому простому делителю, возвращаем кратные парам и так далее.

Считается она за то же время, что и разложение, а через решето — сразу для всех чисел до $n$.