如何获取指数形式的值的模

Question

问题是关于非常大的数的模运算符。

例如，考虑一个要计算排列总数的问题。 考虑一个 90 位数字，其中 9 个数字（1 到 9）中的每一个重复 10 次 所以要计算 90!/(10!)^9)

在阅读了 StackOverflow 上的许多答案后，我使用对数来计算。

现在考虑日志值为 1923.32877864。

现在我的问题是如何显示答案（即 10 ^ log10(value) ）模“m”？

这是计算可能的排列数的最佳方法吗？

编辑 得到了解决方案:)

感谢 duedl0r。

是否按照您使用模乘逆指定的方式进行操作。谢谢:)

Answer 1

我不确定这实际上是否可能和正确，但让我总结一下我的评论并扩展 Miky Dinescu 的答案。

正如 Miky 已经写的：

a × b ≣_m a_m × b_m

您可以在等式中使用它：

90！ / 10!^9 ≣_m x

计算每一项：

90!_米 / 10!^9_米 ≣_米 x

然后找出您的从 10!^9_m 开始的乘法逆元。然后将其倒数乘以 90!_m。

---

更新
这似乎是正确的（至少对于这种情况:)）。我检查了 Wolfram：

(90!/10!^9) mod (10^9+7) = 998551163

这导致得到相同的结果：

90！模 (10^9+7) = 749079870
10！^ 9 mod (10^9+7) = 220052161

进行逆运算：

(220052161 * x) mod(10^9+7) = 1 = 23963055

然后：

(749079870*23963055) 模组(10^9+7) = 998551163

没有证据，但有一些证据表明它可能有效:)

Answer 2

我认为计算以 m 为模的排列总数的方法（其中 m 是任意整数（通常选择为大素数））是使用以下属性：

 (a * b) % m = ((a % m) * (b % m)) % m

考虑到总数N 的排列数是 N！ = 1 * 2 * 3 * .. * N，如果您需要计算N！ % m，您基本上可以将上面的属性应用于模 m 的乘法，并且您有：

 ((((1 * (2 % m)) % m) * (3 % m)) % m) * .. 

编辑

为了计算 90！ / (10!^9) 值，您可以简化因子，然后使用乘法模 m 来计算模 m 的最终结果。

这就是我的想法：

90！ = 10！ * (11 * 12 * .. * 20) * (21 * 22 * .. * 30) * .. * (81 * 82 * .. * 90)

然后您可以将原始表达式重写为：

(10! * ( 11 * 12 * .. * 20) * (21 * 22 * .. * 30) * .. * (81 * 82 * .. * 90)) / (10! * 10! * ... * 10!)

在分子处，您有 9 个因子的乘积 - 将括号中的每个表达式视为一个因子。分母也是如此（有 9 个因数，每个因数等于 10！）。

分母的第一个因素很容易简化。之后，您还有 8 对需要简化。

因此，您可以分解乘积的每一项并简化分母。例如：

11*12*13*14*15*16*17*18*19*20<=> 11 * 2 * 2 * 3 * 13 * 2 * 7 * 3 * 5 * 2 * 2 * 2 * 2 * 17 * 2 * 9 * 2 * 2 * 5

分母始终为： 2 * 3 * 2 * 2 * 5 * 2 * 3 * 7 * 2 * 2 * 2 * 2 * 3 * 3 * 2 * 5

之后简化第二对简化为： 2 * 2 * 11 * 13 * 17 * 19

同样可以应用于后续的每个对，您最终将得到一个简单的乘积，可以使用上面的公式对 m 进行模计算。

当然，有效地实现算法来执行简化将很棘手，因此最终必须有一种现在无法实现的更好的方法。