求二项式系数的欧拉函数
Find euler function of binomial coefficient
我一直在努力解决这个问题：
求二项式系数 C(n, m) = n! / (m! (n - m)!) 模 10^9 + 7 的 Euler's totient function，m <= n < 2 * 10^5.
我的一个想法是，首先，我们可以在线性时间内预先计算从 1 到 n 的所有 i 的 phi(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)!)，我不知道不知道怎么找。
我也一直在考虑分解二项式系数，但似乎没有有效的方法。
如有任何帮助，我们将不胜感激。
首先，将所有数字 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 完成的，但您似乎已经知道除法在 modulo 环中的工作原理。
我一直在努力解决这个问题：
求二项式系数 C(n, m) = n! / (m! (n - m)!) 模 10^9 + 7 的 Euler's totient function，m <= n < 2 * 10^5.
我的一个想法是，首先，我们可以在线性时间内预先计算从 1 到 n 的所有 i 的 phi(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)!)，我不知道不知道怎么找。
我也一直在考虑分解二项式系数，但似乎没有有效的方法。
如有任何帮助，我们将不胜感激。
首先，将所有数字 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 完成的，但您似乎已经知道除法在 modulo 环中的工作原理。