如何計算a!/(b1! b2! ... bm!) modulo p，p質數在哪里？a和的階乘b可能很大（long long int不夠），所以我需要傳遞給模數。
uj5u.com熱心網友回復：
如果a、bs 和p相當小，則更喜歡@KellyBundy 的取消因子或計算素因子的方法。
乘法和模運算
給定整數m和n其他整數k：
(m * n) modulo k = ((m modulo k) * (n mod k)) modulo k
這允許計算大乘積modulo p而不用擔心溢位，因為我們總是可以將引數保持在 range 內[0, k)。
例如a! modulo k在 python 中計算階乘：
def fact(a, k):
if a == 0:
return 1
else:
return ((a % k) * fact(a - 1, k)) % k
除法和模運算
如果p是一個素數，那么對于任何n不能被 整除p的整數，我們可以找到一個整數，我將其稱為inv(n)：
(n * inv(n)) modulo p = 1
這個數稱為 的模逆。n有多種演算法可以找到模逆，我不會在此處描述（但請參見此處的示例）。
現在，給定整數n和m，并假設它m / n是整數，我們可以應用規則：
(m / n) modulo p = (m * inv(n)) modulo p
因此，只要我們可以計算模逆，我們就可以將除法轉換為乘法，然后應用前面的規則。
uj5u.com熱心網友回復：
另一種方法，將因子列出1到a，然后取消所有除數，然后乘以模 p：
#include <iostream>
#include <vector>
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
int a = 60;
std::vector<int> bs = {13, 7, 19};
int p = 10007;
std::vector<int> factors(a);
for (int i=0; i<a; i )
factors[i] = i 1;
for (int b : bs) {
while (b > 1) {
int d = b--;
for (int& f : factors) {
int g = gcd(f, d);
f /= g;
d /= g;
}
}
}
int result = 1;
for (int f : factors)
result = result * f % p;
std::cout << result;
}
列印 5744，與此 Python 代碼相同：
from math import factorial, prod
a = 60
bs = [13, 7, 19]
p = 10007
num = factorial(a)
den = prod(map(factorial, bs))
print(num // den % p)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/417562.html
標籤：