c++ - C++ 中的模幂运算

Question

我的模幂代码有问题，尽管使用两种不同的伪代码源将代码写了三遍，但我仍无法发现问题。我已经阅读了关于 SE 上 C++ 中模幂运算的其他问题，但这对我没有帮助。这是我最后的代码，我认为是用更简单但不太理想的方式编写的:

#include<iostream>
using namespace std;

// base ^ exponent mod modulus 
unsigned mulmod1(unsigned base, unsigned exponent, unsigned modulus) {
    int result = 1;
    while(exponent > 0){
        if(exponent % 2 == 1)
            result = (result * base) % modulus;
        exponent >>= 1;
        base = (base * base) % modulus;
    }
  return result;
}

int main(){

//9688563^45896 mod 71 = 30
//12^53 mod 7 = 3

cout<<mulmod1(9688563,45896 ,71)<<"\n";   //gives 10 instead of 30
cout<<mulmod1(12,53,7)<<"\n";             //gives correct answer 3

return 0;
}

Answer 1

清理函数 mulmod1 的输入! unsigned 不能容纳 9688563*9688563。如果你做对了，你“只”需要一个可以容纳 modulus * modulus(当然还有你的输入数字)的数据类型来正确执行模幂运算。