C++ 怎么计算会溢出的大数乘方

2025-02-01 15:00:19

推荐回答（3个）

回答1：

如果你坚持要算这么大的数，那就先分配足够的空间，比如说3^93，就至少要17字节的内存，分段相乘，每次加上进位项，你可以参考以前4字节整形数据乘法的实现方式（以前是16位的寄存器，一次只能处理16位的数据，所以要分段处理）。不过还是建议你优化算法，尽量不算这么大的数。

回答2：

若求(a * b) % c，
设 a % c = i, b % c = j，则 a = m * c + i, b = n * c + j (m, n为整数)
推导可知：
a * b = (m * c + i) * (n * c + j) = (m*n*c + m*j + n*i) * c + i * j
则 (a * b) % c = (i * j) % c
总结就是： (a*b) % c = ((a%c) * (b%c)) % c

所以，只要把a^b×c^d适当分组，每组乘积分别取模后相乘，然后再取模。
结果是一样的，同时避免溢出。

回答3：

你不模除肯定溢出啊，不模除要么保留进位部分，要么保留余数部分，肯定信息不完整了