模幂运算的麻烦

Question

我正在尝试解决一个问题，我们必须输出给定数字n ^ p的最后一位。

int modularExponentiation(int n, long long p, int m){
    if(p == 0) return 1;
    if(p & 1)
        return (n % m * modularExponentiation((n*n) % m, p / 2, m) % m) % m;//line 4
    return modularExponentiation((n*n) % m, p / 2, m) % m;
}

在此递归代码中，这里我们通过在第4行中应用模来更改临时结果。这将不会对最终答案带来任何改变？例如，如果在任何中间阶段答案是81 ^ 4，在81处应用％10并将其替换为1，会不会改变最终结果？

Answer 1

否，这不会影响结果，因为(a*b)%m == ((a%m) * (b%m))%m。幂运算当然只是重复乘法，因此适用相同的原理。

（（81 ^ 4）％10）小到可以手动尝试。继续，写出来。

Answer 2

对于模块化的加法和乘法，您可以在每个步骤中使用一个mod，它不会影响结果。实际上，这就是您supposed进行模幂运算以避免溢出的方式。因此，您的最终功能将如下所示：

long long modExp(long long n, long long p, long long m) {
    if (p == 0) {
        // m could be 1 you never know
        return 1 % m;
    }
    n %= m;
    return (n * modExp(n, p - 1, m)) % m;
}