C++：快速模幂

Question

我是一名计算机科学的学生，我有一个问题，我必须使用快速模块指数。

使用我编写的代码，校正器告诉我，在某些情况下，输出是不正确的，但不应该是这样。

unsigned long long int pow(int a, int n, int M)
{
    if(n==0)
        return 1;
    if(n==1)
        return a;
    unsigned long long tmp=pow(a, n/2, M)%M;
    if(n%2==0)
        return ((tmp)*(tmp))%M;
    return ((tmp*tmp)*(a%M))%M;
}

相反，使用其他代码，我通过了所有的测试用例。

unsigned long long int pow(int a, int n, int M)
{
    if(n==0)
        return 1;
    if(n==1)
        return a;
    unsigned long long tmp;
    if(n%2==0){
        tmp=pow(a, n/2, M)%M;
        return (tmp*tmp)%M;
    }
    tmp=pow(a, n-1, M)%M;
    return (tmp*(a%M))%M;
}

所以我的问题是，为什么第一段代码我没有通过所有的测试用例？

Answer 1

首先，如果是n == 1，返回值应该是a % M，而不是a。其次，产品(tmp * tmp) * (a % M)可能溢出，并应计算为((tmp * tmp) % M) * (a % M)。

条件n == 1不需要任何特殊处理，代码可以简化为：

unsigned long long int pow(unsigned int a, unsigned int n, unsigned int m) {
    if (n == 0)
        return 1;

    auto tmp = pow(a, n / 2, m) % m;
    tmp *= tmp;
    if (n % 2)
        tmp = (tmp % m) * (a % m);
    return tmp % m;
}