What is the need for the expression (num + mod)% mod?

Question

What is the need for the expression ans = (ans + mod) % mod in this program?

Suppose mod = 10^9+7 . This function computes a to degree b in the operation mod in O (log (n)) complexity:

 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

The most common use of such a design is to make sure that the result is non-negative. The operator% standard behaves differently for positive and negative arguments: for example, 4%3==1 , but (-2)%3==-2 , while you can expect (-2)%3==1 and (-2)/3==-1 , which is mathematically more correct.

This behavior can often cause problems when using modular arithmetic, and this mod add trick is often used to obtain a mathematically more correct non-negative result. Instead of just writing a%b , if a can be negative, (a%b+b)%b written.

However, using it in code in your question is strange. In this case, it is easier to assume that a is positive before calling the power function from the main code (for example, by making a main call, for example, power((a%mod+mod)%mod, b) ). Probably, the author simply wanted to gain additional confidence in the correctness, although he was not needed.