c++ - 求二项式系数的欧拉函数

Question

我一直在尝试解决这个问题:

查找Euler's totient function二项式系数C(n, m) = n! / (m! (n - m)!)模 10^9 + 7, m <= n < 2 * 10^5 .

我的想法之一是，首先，我们可以预先计算phi(i)的值。对于线性时间内从 1 到 n 的所有 i，我们还可以使用例如费马小定理计算从 1 到 n 模 10^9 + 7 的所有数字的逆。之后，我们知道，一般来说，phi(m * n) = phi(m) * phi(n) * (d / fi(d)), d = gcd(m, n) 。因为我们知道gcd((x - 1)!, x) = 1, if x is prime, 2 if x = 4, and x in all other cases ，我们可以计算出phi(x!)在线性时间内对 10^9 + 7 求模。然而，在最后一步，我们需要计算phi(n! / ((m! (n - m)!) ，(如果我们已经知道阶乘函数)，所以，如果我们使用这种方法，我们必须知道 gcd(C(n, m), m! (n - m)!) ，但我不知道如何找到它。

我也一直在考虑对二项式系数进行因式分解，但似乎没有有效的方法来做到这一点。

如有任何帮助，我们将不胜感激。

Answer 1

首先，将所有数字 1..(2*10^5) 分解为素数幂的乘积。

现在，对 n!/k! 进行因式分解= n(n-1)(n-2)...(n-k+1) 作为素数幂的乘积，将各个部分的因子相乘。因式分解 (n-k)!作为素数幂的产物。从前者中减去后者的权力(以解释分歧)。

现在你已经得到了 C(n, k) 作为素数幂的乘积。使用公式 phi(N) = N * prod(1 - 1/p for p|N) 计算 phi(C(n, k))，这很简单，因为您已经计算了所有素数的列表在第二步中除 C(n, k) 的幂。

例如:

phi(C(9, 4)) = 9*8*7*6*5 / 5*4*3*2*1
9*8*7*6*5 = 3*3 * 2*2*2 * 7 * 3*2 * 5 = 7*5*3^3*2^4
5*4*3*2*1 = 5 * 2*2 * 3 * 2 * 1 = 5*3*2^3

9*8*7*6*5/(5*4*3*2*1) = 7*3^2*2

phi(C(9, 4)) = 7*3^2*2 * (1 - 1/7) * (1 - 1/3) * (1 - 1/2) = 36

我已经用整数而不是整数 mod M 来完成它，但看起来你已经知道除法在模环中是如何工作的。