这个程序中的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;
}
最佳答案
这种结构最常见的用法是确保结果是非负的。标准 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)
这样的主调用。可能作者只是想获得额外的正确性保证,尽管这不是必需的。
关于c++ - (num+mod)%mod 语句需要什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31289961/