Common Math Formulas and Tricks Used in Competitive Programming

Правка en1, от Hamsar, 2026-04-24 09:48:40

1. Basic Arithmetic Formulas

  • Sum of first $$$n$$$ natural numbers:
$$$ \frac{n(n+1)}{2} $$$
  • Sum of squares:
$$$ \frac{n(n+1)(2n+1)}{6} $$$
  • Sum of cubes:
$$$ \left(\frac{n(n+1)}{2}\right)^2 $$$

2. Modular Arithmetic

  • Addition:
$$$ (a + b) \bmod m = (a \bmod m + b \bmod m) \bmod m $$$
  • Multiplication:
$$$ (a \times b) \bmod m = (a \bmod m \times b \bmod m) \bmod m $$$
  • Modular inverse (when $$$m$$$ is prime):
$$$ a^{-1} \equiv a^{m-2} \pmod{m} $$$

3. GCD and LCM

$$$ \text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)} $$$
$$$ \gcd(a, b) = \gcd(b, a \bmod b) $$$

4. Combinatorics

$$$ nCr = \frac{n!}{r!(n-r)!} $$$
$$$ nCr = (n-1)C(r-1) + (n-1)Cr $$$

5. Bit Manipulation

  • Power of 2 check:
$$$ n & (n-1) = 0 $$$
  • XOR properties:
$$$ a \oplus a = 0 $$$
$$$ a \oplus 0 = a $$$

6. Prefix Sums

$$$ \text{prefix}[i] = \text{prefix}[i-1] + a[i] $$$
$$$ \text{sum}(l, r) = \text{prefix}[r] - \text{prefix}[l-1] $$$

7. Geometry

  • Distance formula:
$$$ \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} $$$
  • Triangle area:
$$$ \frac{1}{2} |x_1(y_2 - y_3) + x_2(y_3 - y_1) + x_3(y_1 - y_2)| $$$

8. Pigeonhole Principle

If $$$n+1$$$ objects are placed into $$$n$$$ boxes, at least one box contains more than one object.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Hamsar 2026-04-24 09:48:40 1427 Initial revision (published)