计算 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);
    }
}

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

例如。 (pow(x,n/2,d))*(pow((x),n/2,d))这里两个big int值相乘会导致数据类型溢出

计算 pow(x,n)%d 时的极端情况

Corner cases while calculating pow(x,n)%d

algorithm

pow

mod