Jaki jest najskuteczniejszy sposób obliczenia silni modulo a prime?

Czy znasz jakiś algorytm, który skutecznie oblicza silnię po module?

Na przykład chcę zaprogramować:

for(i=0; i<5; i++)
  sum += factorial(p-i) % p;

Ale pjest duża liczba (prime) stosowania bezpośrednio silnia $(p \leq 10^ 8)$ .

W Pythonie to zadanie jest naprawdę łatwe, ale naprawdę chcę wiedzieć, jak zoptymalizować.

(Ta odpowiedź została pierwotnie zamieszczona przez pytającego jonaprieto wewnątrz pytania).

Pamiętam twierdzenie Wilsona i zauważyłem małe rzeczy:

W powyższym programie lepiej jest napisać:

$$\begin{align} (p-1)! &\equiv -1 &\pmod p\\ (p-2)! &\equiv (p-1)! (p-1)^ {-1} \equiv \bf{1} &\pmod p\\ (p-3)! &\equiv (p-2)! (p-2)^ {-1} \equiv \bf{(p-2)^{-1}} &\pmod p\\ (p-4)! &\equiv (p-3)! (p-3)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}} &\pmod p\\ \ (p-5)! &\equiv (p-4)! (p-4)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}}\bf{(p-4)^{-1}} &\pmod p\\ \end{align}$$

I możesz znaleźć ponieważ nazwa , więc dzięki rozszerzonemu algorytmowi euklidesowemu możesz znaleźć wartość , czyli moduł odwrotny.$(p-i)^{-1}$$\operatorname{gcd}(p, p-i) = 1$$(p-i)^{-1}$

Możesz także zobaczyć te same przystawki, na przykład: więc suma jest równa: i jeśli na początku rozłożymy czynniki na czynniki, otrzymamy I, voila, moduł odwrotności jest bardziej wydajny niż silnia.

$$\begin{align*} (p-5)! &\equiv (p-24)^{-1}&\pmod p\\ (p-4)! &\equiv (p+6)^{-1}&\pmod p\\ (p-3)! &\equiv (p-2)^{-1} &\pmod p\\ (p-2)! &\equiv 1&\pmod p\\ (p-1)! &\equiv -1&\pmod p\\ \end{align*}$$ $$(-24)^{-1}+(6)^{-1} +(-2)^{-1}$$ $$8\cdot (-24)^{-1} \pmod p$$

Przykład, który publikujesz, jest bardzo blisko związany z problemem Eulera # 381. Więc opublikuję odpowiedź, która nie rozwiąże problemu Eulera. Napiszę, jak możesz obliczyć silnię modulo liczbę pierwszą.

Więc: Jak obliczyć n! modulo p?

Szybka obserwacja: Jeśli n ≥ p, to n! ma współczynnik p, więc wynik wynosi 0. Bardzo szybko. A jeśli zignorujemy wymóg, aby p było liczbą pierwszą, niech q będzie najmniejszym współczynnikiem liczby pierwszej p, a n! moduł p wynosi 0, jeżeli n ≥ q. Nie ma również wielu powodów, aby wymagać, aby p było liczbą pierwszą, aby odpowiedzieć na twoje pytanie.

Teraz w twoim przykładzie (n - i)! dla 1 ≤ i ≤ 5 pojawiły się. Nie musisz obliczać pięciu silni: obliczasz (n - 5) !, mnożymy przez (n - 4) idź zdobądź (n - 4) !, mnoż przez (n - 3), aby uzyskać (n - 3)! itp. Zmniejsza to pracę prawie 5-krotnie. Nie rozwiązuj problemu dosłownie.

Pytanie brzmi: jak obliczyć n! modulo m. Oczywistym sposobem jest obliczenie n !, liczby z grubsza n log n cyfr dziesiętnych i obliczenie reszty modułu p. To ciężka praca. Pytanie: Jak możemy szybciej uzyskać ten wynik? Nie robiąc rzeczy oczywistych.

Wiemy, że ((a * b * c) modulo p = (((a * b) modulo p) * c) modulo p.

Aby obliczyć n !, zwykle zaczynamy od x = 1, a następnie mnożymy x przez 1, 2, 3, ... n. Korzystając ze wzoru modulo, obliczamy n! modulo p bez obliczania n !, zaczynając od x = 1, a następnie dla i = 1, 2, 3, .., n zamieniamy x na (x * i) modulo p.

Zawsze mamy x <p i i <n, więc potrzebujemy tylko wystarczającej precyzji, aby obliczyć x * p, a nie dużo większej precyzji, aby obliczyć n !. Więc obliczyć n! modulo p dla p ≥ 2 wykonujemy następujące kroki:

Step 1: Find the smallest prime factor q of p. If n ≥ q then the result is 0.
Step 2: Let x = 1, then for 1 ≤ i ≤ n replace x with (x * i) modulo p, and x is the result. 

(Niektóre odpowiedzi wspominają twierdzenie Wilsona, które odpowiada tylko na pytanie w bardzo szczególnym przypadku podanego przykładu i jest bardzo przydatne do rozwiązania problemu Eulera # 381, ale ogólnie nie jest przydatne do rozwiązania zadanego pytania).

Oto moje zastosowanie implementacyjne twierdzenia Wilsona:

Funkcję factMOD można wywołać w celu obliczenia (n!)% MOD, gdy MOD-n jest małe w stosunku do n.

Czy ktoś zna inne skuteczne podejście, gdy tak nie jest (np .: n = 1e6 i MOD = 1e9 + 7)?

ll powmod(ll a, ll b){//a^b % MOD
  ll x=1,y=a;
  while(b){
    if(b&1){
      x*=y; if(x>=MOD)x%=MOD;
    }
    y*=y; if(y>=MOD)y%=MOD;
    b>>=1;
  }
  return x;
} 
ll InverseEuler(ll n){//modular inverse of n
  return powmod(n,MOD-2);
}
ll factMOD(ll n){ //n! % MOD efficient when MOD-n<n
   ll res=1,i;
   for(i=1; i<MOD-n; i++){
     res*=i;
     if(res>=MOD)res%=MOD;
   }
   res=InverseEuler(res);   
    if(!(n&1))
      res= -res +MOD;
  }
  return res%MOD;
}