计算POW(x，n)％d的角案例

Question

我为x的正值和负值提出了上述问题的工作代码。而且，大多数情况的答案是正确的，但是该代码在角色案例中失败了，我似乎找不到问题是什么！我缺少什么条件：`

int pow(int x, int n, int d) {
int i=0,rem=1;
long long l;
    if(x==0)
    {
        return 0;
    }
    if(x==1)
    {
        return 1;
    }
    if(n==0)
    {
        return 1;
    }
    x=x%d;
    if(n%2==0||n==0)
    {
        l = ((pow(x,n/2,d))*(pow((x),n/2,d)))%d;
    }
    else
    {
        l = ((x)*(pow(x,(n-1)/2,d))*(pow((x),(n-1)/2,d)))%d;
    }
    if(x<0 && n%2!=0)
    {
        return d+l;
    } 
    else
    {
        return l;
    }
}

`代码给出错误的ANS的情况：

A: 71045970
B : 41535484
C : 64735492  
My Output: 12942068
Actual Output:20805472

Answer 1

这是您的简化版本。

int pow(int x, int n, int d) {
    long long l;
    if(n==0)
    {
        return 1;
    }
    if(n%2==0)
    {
        l = (long long)pow(x,n/2,d);
        return (int)((l * l) % (long long)d);
    }
    else
    {
        //check negative value of x, and make it positive, so that negative values never come in result
        if (x < 0) {
            x += d;
        }
        return (int)(((long long)x * (long long)pow(x,n-1,d)) % (long long)d);
    }
}

我认为您的代码在逻辑上是正确的，但是如果Modulo d值足够大，则在int数据类型上存在数据溢出问题。

例如。(pow(x,n/2,d))*(pow((x),n/2,d))这里两个大的INT值乘法可能会导致数据类型溢出。