algorithm - 请解释这个模指数的代码

Question

这里 x 可能是负数 我无法理解为什么我们在 if(x<0) 条件下写了 d+x 以及为什么我们最后取模 ans%d 因为我们在找到 ans 时已经对 d 取模if-else 条件

public class Solution {
        public int pow(int x, int n, int d) {
    
        long ans;
        if(x==0) return 0;
        if(n==0) return 1;
        if(x<0)  return pow(d+x,n,d);
        
        long temp = pow(x,n/2,d);
        if(n%2==0)
            ans = ((temp%d)*(temp%d))%d;
        else
            ans = ((((x%d)*(temp%d))%d)*(temp%d))%d;
        
        return (int)ans%d;
    
        }
    }

标签： algorithmdata-structuresexponential

Answer 1

根据模幂的定义，

c = x ⁿ % d 其中0 <= c < d

当 x < 0 时，返回的答案可能是否定的。
因此，通过将 x 更改为 x+d，

if(x<0)  return pow(d+x,n,d);

我们试图避免否定答案作为解决方案。

最后你不需要再次执行模数，

(int)ans;

但是，您可以通过将最后一行更改为 , 来完全忽略 x < 0 的情况

return (int)(ans+d)%d

代码，

public class Solution {
    public int pow(int x, int n, int d) {
    
        long ans;
        if(x==0) return 0;
        if(n==0) return 1;
        
        long temp = pow(x,n/2,d);
        if(n%2==0)
            ans = ((temp%d)*(temp%d))%d;
        else
            ans = ((((x%d)*(temp%d))%d)*(temp%d))%d;
        
        return (int)(ans+d)%d;
    
        }
    }