title: Math & Number Theory —
Math & Number Theory
Math and number theory topics are frequently used in competitive programming for problems involving primes, divisibility, and modular arithmetic.
Applications
- Prime numbers
- GCD/LCM
- Modular arithmetic
1. The Building Blocks: Primality & Divisibility
A number $n$ is prime if its only divisors are $1$ and $n$ itself. To check this efficiently:
- The Basic Way $O(n)$: Check every number from $2$ to $n-1$.
- The Fast Way $O(\sqrt{n})$: You only need to check up to $\sqrt{n}$. If $n$ has a divisor larger than $\sqrt{n}$, it must have a corresponding divisor smaller than $\sqrt{n}$.
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true; // Ensures the function returns true if no divisors are found
}
2. Greatest Common Divisor (GCD)
The GCD (Greatest Common Divisor) of two numbers $a$ and $b$ is the largest number that divides both $a$ and $b$.
On Codeforces, you will often see problems asking for the GCD of an array.
- Euclidean Algorithm: Instead of listing all factors, use the property:
- In C++: You don’t even need to write the function! Just use
__gcd(a, b)from<algorithm>.
3. Modular Arithmetic (The “Remainder” Math)
Most Codeforces problems ask you to output the answer “modulo $10^9 + 7$”. This is because the actual answer is too large to fit in a long long.
Some important modular arithmetic properties:
\[(a + b) \bmod m = \left[(a \bmod m) + (b \bmod m)\right] \bmod m\] \[(a \times b) \bmod m = \left[(a \bmod m) \times (b \bmod m)\right] \bmod m\]Important: Always use long long when multiplying before taking the modulo to avoid overflow!
