Как найти количество делителей числа комбинаторика

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

Из различных разделов математики в спортивном программировании чаще всего
встречаются элементы элементарной теории чисел. В этом разделе значительную
роль имеет разложение числа на простые множители. Простыми называются такие
числа, которые не имеют делителей кроме 1 и самого себя. Ряд простых чисел
выглядит так:

[2, 3, 5, 7, 11, 13, 17, 19, 23, ldots]

Все остальные натуральные числа (кроме 1) называются составными, так как их
можно представить в виде произведения нескольких простых чисел. Например:

[12 = 2 * 2 * 3]

Часто это записывается со степенями простых множителей:

[12 = 2^2 * 3^1]

Таким образом, любое число можно представить в виде произведения простых
множителей следующим образом:

[x = p_1^{alpha_1} * p_2^{alpha_2} * ldots * p_n^{alpha_n} = prodlimits_i {p_i^{alpha_i}}]

Согласно основной теореме арифметики, каждому числу однозначно
соответствует такое представление, поэтому разложение числа на простые
множители тесно связано с некоторыми его свойствами, и часто используется
в решении задач.

Проверка числа на простоту

Чтобы проверить, является ли натуральное число (x) простым, достаточно просто
проверить, существует ли в отрезке ([2;sqrt{x}]) число, на которое делится (x).
Это достаточно очевидно: если бы существовало такое число (y), что (x) делится
на (y) и (sqrt{x} < y < x), то гарантированно существовало бы и число
(z = x/y), которое было бы меньше корня, а значит, изначального условия хватило
бы для проверки на простоту.

Реализация на C++:

1
2
3
4
5
6
7
8
9



bool is_prime(int x) {
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) {
            return false;
        }
    }

    return true;
}






Сложность этого алгоритма (O(sqrt{N})). Существуют алгоритмы, позволяющие

выполнять эту проверку быстрее (порядка (O(log^6 N))), но они исключительно

редко применяются в спортивном программировании.
Факторизация
Факторизацией называется разложение числа на простые множители. Алгоритм

факторизации основывается на тех же идеях, что и алгоритм проверки на простоту,

приведённый выше. А именно: если у числа существует простой делитель, отличный

от него самого, то он не превышает корня из числа. Для факторизации числа нужно

перебрать все числа в промежутке ([2;sqrt{x}]), и попытаться разделить (x) на

каждое из них по очереди.
Реализация на C++ (Сложность: (O(sqrt{N}))):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16



vector<int> factorize(int x) {
    vector<int> factors;

    for (int i = 2; i <= sqrt(x); i++) {
        while (x % i == 0) {
            factors.push_back(i);
            x /= i;
        }
    }

    if (x != 1) {
        factors.push_back(x);
    }

    return factors;
}






Корректность этого алгоритма доказать также несложно. Заметим, что если при

факторизации числа (x) мы нашли делитель (y), то нам, по факту, осталось

факторизовать число (x/y). Поэтому мы можем смело разделить число (x) на (y)

и продолжить работу алгоритма. Мы можем не начинать проверку сначала, так как

число (x/y) гарантированно не имеет делителей меньше (y), иначе мы бы их уже

нашли при факторизации (x).
Также очевидно, что все множители, найденные алгоритмом будут простыми.

Можно заметить, что каждый раз алгоритм находит минимальный из всех делителей

числа, и делит на него само число. Минимальный возможный делитель числа всегда

будет простым.
И наконец, используя доказательство из предыдущего раздела, если у числа нет

делителей меньше либо равных его корню, то оно простое. Этот случай

обрабатывается отдельной проверкой после цикла.
Также можно реализовать алгоритм в виде поиска пар ((p_i, alpha_i)), где

(p_i) — множитель, (alpha_i) — его степень:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16



map<int, int> factorize(int x) {
    map<int, int> factors;

    for (int i = 2; i <= sqrt(x); i++) {
        while (x % i == 0) {
            factors[i]++;
            x /= i;
        }
    }

    if (x != 1) {
        factors[x]++;
    }

    return factors;
}






Поиск делителей
Поиск делителей числа и разложение его на множители — разные понятия,

хотя термины в какой-то степени схожи. Под делителями числа подразумевают

все числа, на которые оно делится. Пример для числа 20:



Множители
(2, 2, 5)


Делители
(1, 2, 4, 5, 10, 20)



Алгоритм поиска делителей числа (x) во многом похож на другие алгоритмы,

приведённые выше. Мы рассматриваем делители парами: для каждого делителя (y)

мы учитываем соответствующий ему (x/y). Один из этих делителей гарантированно

не превышает (sqrt{x}), поэтому, как и раньше, мы можем рассматривать только

промежуток ([1;sqrt{x}]).
Реализация на C++ (Сложность: (O(sqrt{N}))):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16



vector<int> find_dividers(int x) {
    vector<int> dividers;

    for (int i = 1; i <= sqrt(x); i++) {
        if (x % i == 0) {
            dividers.push_back(i);

            //для корня из x не существует парного делителя
            if (i * i != x) {
                dividers.push_back(x / i);
            }
        }
    }

    return dividers;
}






Количество делителей
В качестве примера математических свойств представления числа в виде простых

множителей приведём связь между характеристиками простых множителей числа и

количеством его делителей.
Для этого давайте определим понятие делителя в контексте простых множителей.

Запишем числа (x) и (y) в следующем виде:
[x = p_1^{alpha_1} * p_2^{alpha_2} * ldots * p_n^{alpha_n}]
[y = p_1^{beta_1} * p_2^{beta_2} * ldots * p_n^{beta_n}]
Если какой-либо простой множитель не входит в разложение одного из чисел,

то его степень в следующих рассуждениях принимается за 0.
Утверждение: частное двух чисел можно записать следующим образом:
[{x over y} = p_1^{alpha_1 — beta_1} * p_2^{alpha_2 — beta_2} * ldots * p_n^{alpha_n — beta_n}]
Так как мы работаем с натуральными числами, это выражение имеет смысл тогда

и только тогда, когда все степени простых множителей целые и неотрицательные.

Отсюда можно выразить условие делимости двух чисел:
[forall i: alpha_i — beta_i ge 0]
или
[forall i: beta_i le alpha_i]
(Если вы не знакомы с подобной записью, (forall i) обозначает “для всех (i)”)
Из этого условия можно легко вывести количество делитей. Ещё раз запишем (x) в виде
[x = p_1^{alpha_1} * p_2^{alpha_2} * ldots * p_n^{alpha_n}]
Вспомним, что любому натуральному числу однозначно соответствует

разложение на простые множители, то есть, набор степеней. Другими словами,

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

(beta_i). С ней связано два условия:
(beta_i ge 0) 

(beta_i le alpha_i)
Значит, каждая из степеней (beta_i) может принимать (alpha_i + 1) различных

значений, и набор степеней (beta) однозначно описывает уникальный делитель.

Используя формулы комбинаторики мы можем выразить количество делителей следующим

образом:
[K = (alpha_1 + 1) * (alpha_2 + 1) * ldots * (alpha_n + 1) = prodlimits_i (alpha_i + 1)]
Реализация на C++:
1
2
3
4
5
6
7
8
9



int dividers_count(map<int, int>& factors) {
    int result = 1;

    for (map<int, int>::iterator it = factors.begin(); it != factors.end(); it++) {
        result *= it->second + 1;
    }

    return result;
}






Реализация на C++11:
1
2
3
4
5
6
7
8
9



int dividers_count(map<int, int>& factors) {
    int result = 1;

    for (auto p: factors) {
        result *= p.second + 1;
    }

    return result;
}






Это всего лишь одно из свойств простых множителей. Единственный способ

научиться решать задачи на эту тему — практика.