algorithm - 在 Mod 不是素数的情况下计算逆 Mod

Question

我要计算的值

对于给定的 N 值，F(N) = (F(N-1) * [((N-R+1)^(N-R+1))/(R^R)]) mod M， 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) 中每个素数的幂。

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

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