Факторизация

Основная теорема арифметики утверждает, что любое натуральное число \(n > 1\) можно факторизовать (разложить) на простые множители, то есть записать в виде \(n = p_1 * p_2 * ... * p_k\), где \(p_1, p_2, ..., p_k\) – простые числа, причём такое представление единственно, если не учитывать порядок следования множителей.

Научимся искать разложение числа \(n\) на простые множители.

Будем перебирать в переменной \(d\) все числа от \(2\) до \(\sqrt{n}\) и делить \(n\) на d до тех пор, пока оно делится. Заметим, что при таком подходе \(n\) всегда будет делиться только на простые числа, так как если в переменной \(d\) записано составное число, то это значит, что до этого мы уже разделили \(n\) на все простые числа, которые являются делителями \(d\). Таким образом, мы нашли все простые делители числа \(n\), не превосходящие \(\sqrt{n}\). Возможно, у нас остался один простой делитель, больший \(\sqrt{}n\) (если бы \(n\) содержало два таких делителя, то их произведение было бы больше \(n\)). Такой делитель хранится в переменной \(n\) после завершения перебора всех значений \(d\).

Асимптотика \(O(\sqrt{n})\).

Также бывает полезным асимптотически оценить количество различных простых делителей \(n\) – \(p_1, p_2, ..., p_k\). Заметим, что деление на каждый делитель уменьшит число \(n\) минимум в два раза, а значит количество \(k\) различных простых делителей есть \(O(log(n))\).

vector<int> factorization(int n) {
   vector<int> p;
   for (int d = 2; d * d <= n; ++d) {
       while (n % d == 0){
           p.push_back(d);
           n /= d;
       }
   }
   if (n > 1)
       p.push_back(n);
   return p;
}

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

Пусть нам необходимо проверить на простоту все числа от 1 до \(n\).

Очевидно, мы можем проверить каждое число по отдельности и получить алгоритм с вычислительной сложностью \(O(n*\sqrt{n})\).

Однако, есть более быстрый алгоритм – решето Эратосфена. Идея проста – запишем ряд чисел \(1 ... n\) и будем вычёркивать сначала все числа, делящиеся на \(2\), кроме самого числа \(2\). Перейдём к следующему числу \(3\), оно не вычеркнуто, значит, является простым. Вычеркнем все числа, делящиеся на \(3\). Четыре окажется вычеркнутым, значит, следующее простое число – \(5\) и так далее. В результате невычеркнутыми останутся простые числа в диапазоне от \(2\) до \(n\).

При этом в алгоритме можно сделать улучшение – вычёркивать все числа, делящиеся на простое \(i\) не от \(2i\), а от \(i^2\), так как все числа от \(2i\) до \((i − 1) * i\) заведомо имеют меньший простой делитель и уже были вычеркнуты.

Асимтотика – \(O(n*log(log(n)))\)

vector<bool> prime(n + 1, true);
prime[0] = prime[1] = false;
for(i = 2; i <= n; ++i) {
    if(!prime[i] || i * i > n)
        continue;
    for (j = i * i; j <= n; j += i)
        prime[j] = 0;
}

Линейное решето

Идея

Основная проблема решета Эратосфена состоит в том, что некоторые числа мы будем помечать как составные несколько раз — столько, сколько у них различных простых делителей. Чтобы достичь линейного времени работы, нам нужно придумать способ, как рассматривать все составные числа ровно один раз.

Обозначим за \(d(k)\) минимальный простой делитель числа \(k\) и заметим следующий факт: у составного числа \(k\) есть единственное представление \(k = d(k) * r\), и при этом у числа \(r\) нет простых делителей меньше \(d(k)\).

Идея оптимизации состоит в том, чтобы перебирать этот \(r\), и для каждого перебирать только нужные множители – а именно, все от \(2\) до \(d(r)\) включительно.

Тогда асимптотика будет \(O(n)\).

Алгоритм

Немного обобщим задачу – теперь мы хотим посчитать для каждого числа \(k\) на отрезке \([2; n]\) его минимальный простой делитель \(d_k\), а не только определить его простоту.

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

Теперь будем перебирать число \(k\) от \(2\) до \(n\). Если это число простое, то есть \(d_k\) = 0, то присвоим \(d_k = k\) и добавим \(k\) в список \(p\).

Дальше, вне зависимости от простоты \(k\), начнём процесс расстановки значений в массиве \(d\) – переберем найденные простые числа \(p_i\), не превосходящие \(d_k\), и сделаем присвоение \(d_{p_i*k} = p_i\).

vector<int> d(n+1, 0);
vector<int> p;
for(int k = 2; k <= n; ++k) {
    if(p[k] == 0) {
        d[k] = k;
        p.push_back(k);
    }
    for (int x : p) {
        if (x > d[k] || x * d[k] > n)
            break;
        d[k * x] = x;
    }
}

Алгоритм требует как минимум в 32 раза больше памяти, чем обычное решето, потому что требуется хранить делитель (int, 4 байта) вместо одного бита на каждое число. Линейное решето хоть и имеет лучшую асимптотику, но на практике проигрывает также и по скорости оптимизированному варианту решета Эратосфена.

Применение

Массив \(d\) позволяет искать факторизацию любого числа k за время порядка размера этой факторизации:

Знание факторизации всех чисел – очень полезная информация для некоторых задач. Линейное решето интересно не своим временем работы, а именно этим массивом минимальных простых делителей.

НОД И НОК

Наибольшим общим делителем (англ. greatest common divisor) целых неотрицательных чисел \(a\) и \(b\) называется наибольшее число \(x\), которое делит одновременно и \(a\), и \(b\).

\(gcd(a, b) = gcd(a - b, b)\)

  • если \(g = gcd(a, b)\) делит и \(a\), и \(b\), то их разность \((a−b)\) тоже будет делиться на g.
  • Никакой больший делитель \(d\) числа \(b\) не может делить число \((a − b)\): если \(d > g\), то d не может делить \(a\), а значит и не делит \((a − b)\).
int gcd(int a, int b) {
    while(b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

Можно показать, что каждые две итерации меньшее число уменьшится хотя бы в два раза, а следовательно алгоритм работает за \(O(log(⁡min(a, b)))\). Эта оценка относится не только к худшему случаю, но и к среднему.

НОК

Наименьшим общим делителем (англ. lowest common divisor) целых неотрицательных чисел \(a\) и \(b\) называется наименьшее число \(x\), которое делится одновременно и на \(a\), и на \(b\).

Из основной теоремы арифметики следует : \(gcd(a, b) * lcm(a, b) = a*b\).

тогда \(lcm(a, b) = \frac{a}{gcd(a, b)}*b\)

Бинарное возведение в степень

Заметим, что для любого числа \(a\) и чётного числа \(n\) выполняется тождество: \(\)a^n = (a^{\frac{n}{2}})^2 = a^{\frac{n}{2}} * a^{\frac{n}{2}}\(\) Если же \(n\) нечётно, то верно следующее: \(\)a^n = a^{n−1} * a\(\)

Так как каждые два перехода \(n\) гарантированно уменьшается хотя бы в два раза, всего будет не более \(2 * log(n)\) шагов, прежде чем мы придём к \(n = 0\). Каждый переход требует ровно одно умножение, и таким образом, мы получили алгоритм, работающий за \(O(log(n))\).

int binpow(int a, int n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1)
        return binpow(a, n - 1) * a;
    else {
        int b = binpow(a, n / 2);
        return b * b;
    }
}

Эта реализация рекурсивная, что работает долго. Попробуем «развернуть» рекурсию и получить итеративную.

Рассмотрим двоичное представление числа \(n\). Результат \(a^n\) можно представить как произведение \(a\) в степенях каких-то степеней двоек. Например, если \(n = 42 = 32 + 8 + 2\), то \(a^{42} = a^{32} * a^{8} * a^{2}\)

Чтобы посчитать это произведение итеративно, пройдемся по всем битам числа \(n\), поддерживая две переменные: непосредственно результат и текущее значение \({a^2}^k\)a, где \(k\) – это номер текущей итерации. На каждом шаге будем домножать \({a^2}^k\) на текущий результат, если \(k\)-тый бит числа \(n\) единичный, и в любом случае возводить её в квадрат, получая \({a^2}^{k+1}\) для следующей итерации.

int binpow(int a, int n) {
    int res = 1;
    while (n != 0) {
        if (n & 1)
            res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

Деление по модулю

Обычные арифметические операции по модулю выполняются не сильно сложнее — просто нужно брать модули и заботиться о переполнении. Например:

c = (a + b) % mod;
c = (a - b + mod) % mod;
c = a * b % mod;

Но вот с делением возникают проблемы — мы не можем просто взять и поделить. Например \(\frac{10}{5} = 2\) (mod \(7\)), но \(\frac{10}{5} \equiv \frac{3}{5} \not= 2\) (mod 7)

Нужно найти некоторый элемент, который будет себя вести как \(\frac{1}{a} = a^{-1}\), и вместо “деления” домножать на него. Такой элемент называется обратным по модулю \(m\). Для \(a = 0\) обратный по модулю элемент не определён, как и при обычном делении.

Малая теорема Ферма говорит, что для любого простого числа \(p\) и любого целого числа \(a\)

\[a^p \equiv a\]

тогда \(a^{p-2} \equiv a{-1}\). Это можно посчитать за \(O(log(p))\) через бинарное возведение в степень.