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 问题。