п!по модулю м, а ^ р по модулю м

Question

Есть ли более быстрый алгоритм для вычисления (n! По модулю m). быстрее, чем сокращение на каждом шаге умножения. А также Есть ли более быстрый алгоритм для вычисления (a ^ p по модулю m) лучше, чем правосторонний двоичный метод.

вот мой код: п! мод м

ans=1
for(int i=1;i<=n;i++)
    ans=(ans*i)%m;

a ^ p mod m

result=1;
while(p>0){
    if(p%2!=0)
        result=(result*a)%m;
    p=(p>>1);
    a=(a*a)%m;
}

Answer 1

Теперь a^n mod m - это O(logn), это Алгоритм модульного экспонирования .

Теперь для другого, n! mod m, предложенный вами алгоритм явно O(n), Очевидно, первый алгоритм работает быстрее.

Answer 2

Стандартный прием для вычисления a^p modulo m заключается в использовании последовательного квадрата.Идея состоит в том, чтобы расширить p в двоичный файл, скажем

p = e0 * 2^0 + e1 * 2^1 + ... + en * 2^n

, где (e0,e1,...,en) - двоичный файл (0 или 1) и en = 1.Затем используйте законы экспонент, чтобы получить следующее расширение для a^p

a^p = a^( e0 * 2^0 + e1 * 2^1 + ... + en * 2^n )
    = a^(e0 * 2^0) * a^(e1 * 2^1) * ... * a^(en * 2^n)
    = (a^(2^0))^e0 * (a^(2^1))^e1 * ... * (a^(2^n))^en

Помните, что каждый ei является либо 0, либо 1, так что они просто говорят вам, какие числа взять.Таким образом, единственные вычисления, которые вам нужны, это

a, a^2, a^4, a^8, ..., a^(2^n)

. Вы можете сгенерировать эту последовательность, возведя в квадрат предыдущее слагаемое.Поскольку вы хотите вычислить ответ mod m, вы должны сначала выполнить модульную арифметику.Это означает, что вы хотите вычислить следующее

A0 = a mod m
Ai = (Ai)^2 mod m for i>1

Тогда ответ будет

a^p mod m = A0^e0 + A1^e1 + ... + An^en

Поэтому вычисление занимает log(p) квадратов и вызывает mod m.

Я не уверен, существует ли аналог для факториалов, но хорошее место для начала было бы найти Теорема Вильсона .Кроме того, вы должны поставить тест на m <= n, в этом случае n! mod m = 0.

Answer 3

Для первого вычисления вам стоит беспокоиться только об операторе мода, если ans > m:

ans=1
for(int i=1;i<=n;i++) {
    ans *= i;
    if (ans > m) ans %= m;
}

Для второго вычисления использование (p & 1) != 0, вероятно, будет намного быстрее, чем использование p%2!=0 (если компилятор не распознает этот особый случай и не сделает это за вас). Затем применяется тот же комментарий об исключении оператора %, если в этом нет необходимости.