java - 反模问题 where gcd(denominator,mod)!=1

Question

如何计算 F(n)%mod 其中 mod 是质数。和 F(n)=n!/(q!^r)%mod....(x^r 代表 pow(x,r) )。

我正在尝试使用费马小定理来计算逆模，但我面临的问题是费马仅在 gcd(denominator,mod)=1 时适用。

那么有没有其他方法可以解决这个问题。

Answer 1

如果模数是质数，您可以使用扩展欧几里得算法计算逆数:

function inverse(x, m)
    a, b, u = 0, m, 1
    while x > 0
        q = b // x # integer division
        x, a, b, u = b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"

如果模数是复合的，只要 x 和 m 互质，该算法仍然有效。如果它们共享一个因子，则逆因子不存在。