Modular Arithmetic is an important topic in Competitive Programming. Some questions involve such big numbers that they can’t even fit in any of the data types. So, modular arithmetic is a method to avoid data overflow.
It states that, for any pair of integers a and b (b is positive), there exist two unique integers q and r such that:
The largest data type in C++ is unsigned long long int, which is of 64-bits and can handle integers from 0 to
Generally, the question statement mentions if modulo needs to be used. The statement that prompts the usage of modulo is:
"Print the answer modulo
Modulo cannot be simply used for arithmetic operations and follows certain rules. The rules are as follows:
-
$(a + b)$ %$mod = ((a$ %$mod) + (b$ %$mod))$ %$mod$ -
$(a * b)$ %$mod = ((a$ %$mod) * (b$ %$mod))$ %$mod$ -
$(a - b)$ %$mod = ((a$ %$mod) - (b$ %$mod) + mod)$ %$mod$
The difference from the general pattern in the case of subtraction can be understood by the following example:
It can be proven that this formula is valid for all values of (a) and (b).
-
$(a / b)$ %$mod = (a * (inverse\ of\ b\ if\ it\ exists))$ %$mod$
Inverse of b exists only when b and mod are co-primes, that is-
I would recommend you to read this article for in depth understanding of Modular Inverse