Блог пользователя Hamsar

Автор Hamsar, история, 7 месяцев назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

Автор Hamsar, история, 7 месяцев назад, По-английски

Checking Odd/Even

if (x & 1) { // x is odd } else { // x is even }

Clearing the Lowest Set Bit

x = x & (x — 1);

Extracting the Lowest Set Bit

int lowest = x & -x;

Counting Set Bits (Brian Kernighan’s Algorithm) int count = 0; while (x) { x &= (x — 1);// clear the lowest set bit count++; }

XOR Swap Trick

a ^= b; b ^= a; a ^= b;

Converting Case for Letters

->Uppercase to Lowercase: char lower = ch | ' ' ;

->Lowercase to Uppercase: char upper = ch & '_' ;

Next Highest Power of 2

unsigned int v = original; v--;// in case v is already a power of 2 v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16;// For 32-bit integers; extend for 64-bit as needed. v++;

Multiply or Divide by Powers of Two int mul = x << 3; // Multiply x by 8 (2^3) int div = x >> 2; // Divide x by 4 (2^2)

Averaging Two Numbers Without Overflow

int average = (x & y) + ((x ^ y) >> 1);

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится