如何计算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)