math - 如何以指数形式取模

Question

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

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

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

现在考虑日志值为 1923.32877864。

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

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

编辑得到了解决方案:)

感谢 duedl0r。

是否按照您使用模乘逆指定的方式进行。谢谢：）

score 1 · Accepted Answer

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

正如米奇已经写道：

a × b ≣<sub>ma _m × b _m

你可以在你的平等中使用它：

90！/ 10!^9 ≣<sub>mx

计算每一项：

90！_m / 10!^9 _m ≣<sub>mx

然后从 10!^9 _m中找出你的乘法逆元。然后将逆数乘以 90！_米。

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

这导致相同的结果：

做相反的事情：

然后：

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

score 0 · Accepted Answer

我认为计算排列总数的方法 modulo 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 为模计算。

当然，有效地实现算法来执行简化将是棘手的，所以最终必须有一个更好的方法让我现在无法理解。

2 回答 2