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 完成了它，但您似乎已经知道除法在模环中是如何工作的。