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

e-maxx algorithm original: C/C++ #algorithm #emaxx #math #number-theory

Task text is translated from Russian for the selected interface language. Code is left unchanged.

Static

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

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

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

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

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

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

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

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

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

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

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

Таким образом, формально Task такая. it is required вычислить

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

, при этом не given

все кратные

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

Algorithm

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

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

(последний

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

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

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

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

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

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

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

операций

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

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

, либо

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

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

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

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

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

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

мы свели

за

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

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

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

, итого Asymptotic complexity Algorithmа получается

Implementation

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

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;

}

Эта Implementation работает за

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;
    }
}

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

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.