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;
}