E016. Вычисление факториала по модулю

emaxx algorithm

#algorithm#emaxx#math#number-theory

Task

Источник: e-maxx.ru/algo, страница PDF 45.

В некоторых случаях необходимо считать по некоторому простому модулю

сложные формулы, которые в том

числе могут содержать факториалы. Здесь мы рассмотрим случай, когда модуль

сравнительно мал. Понятно, что

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

дробей. Действительно, факториал

и все последующие обращаются в ноль по модулю

, однако в дробях

все множители, содержащие

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

Таким образом, формально задача такая. Требуется вычислить

по простому модулю

, при этом не учитывая

все кратные

множители, входящие в факториал. Научившись эффективно вычислять такой факториал, мы сможем быстро вычислять значение различных комбинаторных формул (например, Биномиальные коэффициенты).

Алгоритм

Выпишем этот "модифицированный" факториал в явном виде:

При такой записи видно, что "модифицированный" факториал распадается на несколько блоков длины

(последний

блок, возможно, короче), которые все одинаковы, за исключением последнего элемента:

Общую часть блоков посчитать легко — это просто

, которую можно посчитать программно или

по теореме Вильсона (Wilson) сразу найти

. Чтобы перемножить эти общие части

всех блоков, надо найденную величину возвести в степень по модулю

, что можно сделать за

операций

(см. Бинарное возведение в степень; впрочем, можно заметить, что мы фактически возводим минус единицу в какую-

то степень, а потому результатом всегда будет либо

, либо

, в зависимости от чётности показателя. Значение

в последнем, неполном блоке тоже можно посчитать отдельно за

. Остались только последние элементы

блоков, рассмотрим их внимательнее: И мы снова пришли к "модифицированному" факториалу, но уже меньшей размерности (столько, сколько было

полных блоков, а их было

). Таким образом, вычисление "модифицированного" факториала

мы свели

за

операций к вычислению уже

. Раскрывая эту рекуррентную зависимость, мы получаем, что

глубина рекурсии будет

, итого асимптотика алгоритма получается

Реализация

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

int factmod (int n, int p) {

int res = 1;

while (n > 1) {

res = (res * ((n/p) % 2 ? p-1 : 1)) % p;

for (int i=2; i<=n%p; ++i)

res = (res * i) % p;

n /= p;

}

return res % p;

}

Эта реализация работает за

C# solution

auto-draft, review before submit

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    int factmod (int n, int p) {
            int res = 1;
            while (n > 1) {
                    res = (res * ((n/p) % 2 ? p-1 : 1)) % p;
                    for (int i=2; i<=n%p; ++i)
                            res = (res * i) % p;
                    n /= p;
            }
            return res % p;
    }
}

C++ solution

matched/original

int factmod (int n, int p) {
        int res = 1;
        while (n > 1) {
                res = (res * ((n/p) % 2 ? p-1 : 1)) % p;
                for (int i=2; i<=n%p; ++i)
                        res = (res * i) % p;
                n /= p;
        }
        return res % p;
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    int factmod (int n, int p) {
            int res = 1;
            while (n > 1) {
                    res = (res * ((n/p) % 2 ? p-1 : 1)) % p;
                    for (int i=2; i<=n%p; ++i)
                            res = (res * i) % p;
                    n /= p;
            }
            return res % p;
    }
}

Explanation

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