c++ - 模幂 - 如何减少巨大的模数？

Question

模幂运算的典型方程是 (a + b) MOD n = ((a MOD n) + (b MOD n)) MOD n。如果 a 和 b 非常大，那就太棒了。但是我被要求用一个非常大的 n (2^31 -1) 来做这个幂运算，a 和 b 没问题。

我只需要一种减少 n 的方法。

Answer 1

“(a + b) MOD n = ((a MOD n) + (b MOD n)) MOD n”不是求幂，而是加法。

“(2^31 -1)”不是“巨大的 n”，它是 31 位设置为 1。

由于这些基本假设完全错误，而且问题显然是家庭作业，因此很难在不损害 OP 的情况下提供任何更具体的建议。已经说过的内容应该足以暗示可以解决作业。或者，可以开始一些作业，并发布一个新的 SO 问题。