Menu
What is the need of the statement ans = (ans + mod) % mod in this program ?
Assume that mod = 10^9+7. This function is computing a to the power of b under mod operation 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;
}
808
For a positive integer n, two integers a and b are said to be congruent modulo n (or a is congruent to b modulo n), if a and b have the same remainder when divided by n (or equivalently if a − b is divisible by n ). It can be expressed as a ≡ b mod n. n is called the modulus.
The modulo operator, denoted by %, is an arithmetic operator. The modulo division operator produces the remainder of an integer division. produces the remainder when x is divided by y.
'Modular arithmetic, also known as clock arithmetic, is something we all get used to as soon as we learn to tell the time. It is also a mathematical technique that, perhaps without realising, we rely on every time we do online shopping, internet banking, or send private messages to our friends via social media.
The modulo (or "modulus" or "mod") is the remainder after dividing one number by another. Example: 100 mod 9 equals 1. Because 100/9 = 11 with a remainder of 1. Another example: 14 mod 12 equals 2. Because 14/12 = 1 with a remainder of 2.
The most common usage of such a construct is to make sure the result is non-negative. The standard operator% behaves differently for positive and negative arguments: for example, 4%3==1, but (-2)%3==-2, while you might expect (-2)%3==1 and (-2)/3==-1, which is mathematically more correct.
This behavior can often cause problems when modular arithmetic is used, and this trick of adding mod is often employed to obtain the mathematically more correct non-negative result. Instead of simply writing a%b, if a can be negative, one writes (a%b+b)%b.
However, its usage in the code in your question is strange. In that case, it is easier to assume that a is positive before calling the power function from the main code (for example, by making the main call like power((a%mod+mod)%mod, b)). Probably the author just wanted to get additional assurance of correctness, although it was not needed.
109
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
