快速幂取模算法

• _Mr.Q 发布于
• 1126 收藏

试题 求a^b的后三位数。a,b是整数。 这题也就是计算a^b%1000的值。 解法一 先求出a^b的值，然后计算a^b%m即可。 如果a,b足够大，那么a^b将无法计算出来。所以解法一只适用于a,b都很小的情况。 解法二 解法二会利用如下公式进行计算： 其证明过程如下： 因此a^b%m有如下公式： 按上述公式，就可以避免因为a,b过大，导致溢出的问题。因为每...