In competitive programming, you'll often face problems where the answers are enormous. Standard 64-bit integers in C++ can hold values up to about $9 \times 10^{18}$, but calculations can easily exceed this limit, causing an integer overflow. This is where modular arithmetic comes in. It's a system for dealing with numbers that wrap around after reaching a certain value, called the modulus. Think of a clock: hours wrap around after 12. In programming, we often use a large prime number as the modulus, like $10^9 + 7$. This specific number is large enough to avoid most accidental collisions but small enough to fit within a 64-bit integer when squared.

Division is trickier. We can't just divide and take the modulus. Instead, we multiply by a modular multiplicative inverse. For a number $a$, its modular inverse $a^{-1}$ (modulo $m$) is a number such that $(a \cdot a^{-1}) \pmod{m} = 1$. This inverse only exists if $a$ and $m$ are coprime, which means their greatest common divisor is 1. Since we often use a prime modulus like $10^9 + 7$, this condition is almost always met.

The Greatest Common Divisor (GCD) of two numbers is the largest number that divides both of them without leaving a remainder. A naive approach would be to check every number from 1 up to the smaller of the two numbers, but that's too slow. The Euclidean algorithm provides a much faster, logarithmic-time solution. It's based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number. More efficiently, we can use the remainder.

The algorithm states that $gcd(a, b) = gcd(b, a \% b)$, where $a \% b$ is the remainder when $a$ is divided by $b$. We repeat this process until the second number becomes 0. The first number is then the GCD. Once you have the GCD, finding the Least Common Multiple (LCM) is easy.

What if you need to compute $a^b \pmod{m}$ where $b$ is very large? A simple loop that multiplies $a$ by itself $b$ times would be far too slow. We can do much better using a technique called binary exponentiation (also known as exponentiation by squaring). This algorithm works in logarithmic time, $O(\log b)$. The idea is to use the binary representation of the exponent $b$. For example, to calculate $3^{10}$, we note that $10$ in binary is $1010_2$. This means $10 = 8 + 2$, so $3^{10} = 3^8 \cdot 3^2$. We can compute the powers $3^1, 3^2, 3^4, 3^8, ...$ by repeatedly squaring the previous result.

A related concept is Euler's totient function, $\phi(n)$. This function counts the number of positive integers up to a given integer $n$ that are relatively prime to $n$ (meaning their GCD with $n$ is 1). Euler's theorem states that if $a$ and $n$ are relatively prime, then $a^{\phi(n)} \equiv 1 \pmod{n}$. This is a generalization of Fermat's Little Theorem and is particularly useful for finding modular inverses and reducing large powers. For a prime number $p$, $\phi(p) = p-1$.

Combinatorics is the art of counting arrangements of objects. A common problem is calculating "n choose r", or $nC_r$, which is the number of ways to choose $r$ items from a set of $n$ items without regard to order. The formula is:

A more specific and fascinating counting problem involves Catalan numbers They appear in a surprising number of scenarios, such as: finding the number of correctly matched bracket sequences of length $2n$, or the number of ways a convex polygon with $n+2$ sides can be cut into triangles by connecting vertices. The formula for the $n$-th Catalan number, $C_n$, is:

These mathematical tools are shortcuts. They turn problems that seem to require complex loops or recursion into elegant, efficient calculations. Mastering them is a key step in leveling up your competitive programming skills.