1. Basic Arithmetic Formulas
- Sum of first $$$n$$$ natural numbers:
$$$ \frac{n(n+1)}{2} $$$ $$$ \frac{n(n+1)(2n+1)}{6} $$$ $$$ \left(\frac{n(n+1)}{2}\right)^2 $$$2. Modular Arithmetic
$$$ (a + b) \bmod m = (a \bmod m + b \bmod m) \bmod m $$$ $$$ (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
$$$ n & (n-1) = 0 $$$ $$$ 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
$$$ \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} $$$ $$$ \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.
also , n%a = n-a(n//a)
This helps convert mod constraints into intervals. For example, n%a≤k⇒n∈[aq,aq+k] where q=n//a.
Very helpful for counting problems and block decomposition.
in the power of 2 check.
if n==0, it will be true, so we have to check if n>0 first.