algorithm - 计算 Mod 不是素数的逆 Mod

Question

我想计算价值

F(N) = (F(N-1) * [((N-R+1)^(N-R+1))/(R^R)]) mod M 对于给定的 N,R 和 M 值.

这里 A^B 显示 A 幂 B 而不是任何按位运算

这里 M 不必是素数。如何解决这个问题？请帮忙，因为如果 M 是素数，那么找到 R^R mod M 的倒数就不会那么困难了。

但是因为 M 可以是从 1 到 10^9 的任何值。我无法解决这个问题。

N 可以介于 1 和 10^5 之间，并且 R 小于或等于 N。

Answer 1

假设您以某种方式知道除法的结果是一个整数：

由于 N 和 R 很小，您可以通过计算 N-R+1 和 R 的素数分解来做到这一点。

如果我们知道R=p^a...q^b那R^R = p^(Ra)...q^(Rb)。

同样，您可以计算出 中每个素数的幂(N-R+1)^(N-R+1)。

R^R从素数的幂中减去素数的幂(N-R+1)^(N-R+1)，得到结果中每个素数的幂。

然后，您可以使用标准二进制取幂例程来计算模 M 的结果，而无需求逆。