c++ - (num+mod)%mod 语句需要什么？

Question

这个程序中的ans = (ans + mod) % mod语句需要什么？

假设 mod = 10^9+7。此函数在 O(log(n)) 复杂度的模运算下计算 a 的 b 次方:

long long power(long long a, long long b)
{
    if (b == 0) 
        return 1ll;
    long long ans = power(a, b/2);
    ans = (ans * ans) % mod;
    ans = (ans + mod) % mod;
    if(b % 2 == 1)
        ans = (ans * a) % mod;
    ans = (ans + mod) % mod;
    return ans;
}

Answer 1

这种结构最常见的用法是确保结果是非负的。标准 operator% 对正参数和负参数的行为不同:例如，4%3==1，但 (-2)%3==-2 ，而您可能期望 (-2)%3==1 和 (-2)/3==-1，这在数学上更正确。

当使用模运算时，这种行为通常会导致问题，而这种添加 mod 的技巧通常用于获得数学上更正确的非负结果。如果a可以为负，则不是简单地写a%b，而是写(a%b+b)%b。

但是，它在您问题的代码中的用法很奇怪。在这种情况下，在从主代码调用 power 函数(例如，通过使像 power((a%mod+mod)%mod, b) 这样的主调用。可能作者只是想获得额外的正确性保证，尽管这不是必需的。