这个程序中声明ans =(ans mod)％mod的需要是什么？
假设mod = 10 ^ 9 7.该函数在O(log(n))复杂度的mod操作下计算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;
}
解决方法
这种结构的最常见用法是确保结果是非负的.对于正面和负面参数,标准运算符％的行为有所不同：例如,4％3 == 1,但是(-2)％3 == – 2,而您可能期望(-2)％3 == 1和( – 2)/ 3 == – 1,这在数学上更正确.
当使用模运算时,这种行为通常会引起问题,并且这种添加mod的技巧通常用于获得数学上更正确的非负结果.不是简单地写一个％b,如果a可以是负数,则写入(a％b b)％b.
但是,它在您的问题中的代码中的使用是奇怪的.在这种情况下,在从主代码调用幂函数之前更容易假设a是正数(例如,通过使主调用像power((a％mod mod)％mod,b)).可能作者只是想获得正确性的额外保证,尽管不需要.
