🔢 АРИФМЕТИКА И ПОСЛЕДОВАТЕЛЬНОСТИ

Суммы прогрессий

1. Арифметическая прогрессия 1..n
   sum = n * (n + 1) // 2
   Пример: Сумма чисел от 1 до 100 = 100×101/2 = 5050

2. Сумма квадратов
   1² + 2² + ... + n² = n * (n + 1) * (2n + 1) // 6
   Пример: Для n=3: 1+4+9=14 = 3×4×7/6=14

3. Сумма кубов
   1³ + 2³ + ... + n³ = (n * (n + 1) // 2)²
   Пример: Для n=3: 1+8+27=36 = (3×4/2)²=6²=36

4. Сумма арифметической прогрессии
   a + (a+d) + ... + (a+(n-1)d) = n*(2a + (n-1)*d) // 2
   Пример: 3+5+7+9 (n=4, a=3, d=2) = 4×(2×3 + 3×2)/2 = 24

5. Геометрическая прогрессия
   a + a*r + a*r² + ... + a*r^(n-1) = a*(rⁿ - 1)/(r - 1) для r≠1

Формулы комбинаторики

6. Количество пар (рукопожатия)
   Из n элементов: n * (n - 1) // 2
   Пример: 10 людей = 10×9/2=45 handshakes

7. Количество подмассивов/подотрезков
   В массиве длины n: n * (n + 1) // 2
   Пример: [a,b,c] → 6 подмассивов: [a],[b],[c],[a,b],[b,c],[a,b,c]

8. Количество подпоследовательностей
   2ⁿ - 1 (непустые), 2ⁿ (с пустой)
   Пример: [a,b] → 3: [a],[b],[a,b]

9. Треугольное число
   T_n = n*(n+1)//2 (то же, что сумма 1..n)

🔢 ДЕЛИМОСТЬ И ОСТАТКИ

10. Проверка чётности

    if n & 1:    # нечётное (бит младшего разряда = 1)
    if n % 2 == 0:  # чётное
    

11. Остаток от деления (особые случаи)

    • (a + b) % m = (a%m + b%m) % m
    • (a * b) % m = (a%m * b%m) % m
    • a % b = a - (a // b) * b (определение)

12. Проверка делимости на 3
    Сумма цифр делится на 3 → число делится на 3
    Пример: 123 → 1+2+3=6 делится на 3 → 123 делится

13. Проверка делимости на 4
    Последние 2 цифры образуют число, делящееся на 4
    Пример: 1236 → 36 делится на 4 → 1236 делится

14. Проверка делимости на 9
    Сумма цифр делится на 9

15. Наибольший общий делитель (НОД)

    import math
    math.gcd(a, b)
    # Или алгоритм Евклида:
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    

    Свойство: gcd(a, b) * lcm(a, b) = a * b

16. Наименьшее общее кратное (НОК)
    lcm(a, b) = a * b // gcd(a, b)

🔢 БИТОВЫЕ ОПЕРАЦИИ

Базовые операции

17. Проверка i-го бита

    bit = (n >> i) & 1  # i-й бит (считая с 0 справа)
    if n & (1 << i):    # альтернатива
    

18. Установка i-го бита в 1
    n = n | (1 << i)

19. Установка i-го бита в 0
    n = n & ~(1 << i)

20. Переключение i-го бита
    n = n ^ (1 << i)

21. Извлечение младшего бита (LSB)
    lsb = n & -n # полезно для Fenwick tree

22. Удаление младшего бита
    n = n & (n - 1) # используется в подсчёте единиц

Полезные трюки

23. Число является степенью двойки
    (n & (n - 1)) == 0 and n > 0
    Пример: 8 (1000) & 7 (0111) = 0

24. Округление до следующей степени двойки

    def next_power_of_two(n):
        n -= 1
        n |= n >> 1
        n |= n >> 2
        n |= n >> 4
        n |= n >> 8
        n |= n >> 16
        return n + 1
    

25. Подсчёт единичных битов (popcount)

    bin(n).count('1')
    # Или быстрее:
    def popcount(n):
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count
    

26. Маска всех битов до k
    mask = (1 << k) - 1 # k младших битов в 1
    Пример: k=3 → mask=7 (111 в бинарном)

27. Извлечение нескольких битов
    bits = (n >> start) & ((1 << length) - 1)

28. Обмен значений без временной переменной

    a ^= b
    b ^= a
    a ^= b
    # Только для целых чисел!
    

🔢 МАТРИЦЫ И ГЕОМЕТРИЯ

Поворот матрицы

29. Поворот на 90° по часовой

    # Для квадратной матрицы n×n
    def rotate_clockwise(matrix):
        n = len(matrix)
        # Транспонирование
        for i in range(n):
            for j in range(i+1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        # Отражение по вертикали
        for i in range(n):
            matrix[i].reverse()
        return matrix
    

    Формула для элемента: new[i][j] = old[n-1-j][i]

30. Поворот на 90° против часовой
    Транспонирование + отражение по горизонтали
    Формула: new[i][j] = old[j][n-1-i]

Работа с координатами

31. Манхэттенское расстояние
    dist = |x1 - x2| + |y1 - y2|

32. Евклидово расстояние
    dist = sqrt((x1-x2)² + (y1-y2)²)

33. Проверка на одной линии
    Точки (x1,y1), (x2,y2), (x3,y3) коллинеарны если:
    (y2-y1)*(x3-x1) == (y3-y1)*(x2-x1)

34. Площадь треугольника по координатам
    area = 0.5 * abs(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))

35. Векторное произведение (cross product)
    cross = x1*y2 - x2*y1
    Положительно → поворот против часовой,
    Отрицательно → по часовой,
    0 → коллинеарны

🔢 МНОЖЕСТВА И КОМБИНАТОРИКА

Операции с множествами (теория)

36. Мощность объединения
    |A ∪ B| = |A| + |B| - |A ∩ B|

37. Мощность объединения трёх
    |A ∪ B ∪ C| = |A|+|B|+|C| - |A∩B|-|A∩C|-|B∩C| + |A∩B∩C|

38. Принцип включения-исключения (общий)
    Для множеств A₁...Aₙ:
    |⋃A_i| = Σ|A_i| - Σ|A_i∩A_j| + Σ|A_i∩A_j∩A_k| - ...

Биномиальные коэффициенты

39. Сочетания (C(n,k))
    C(n,k) = n! / (k! * (n-k)!)
    Треугольник Паскаля: C(n,k) = C(n-1,k-1) + C(n-1,k)

40. Количество перестановок

    • Всех элементов: n!
    • С повторениями: n! / (n₁! * n₂! * ...)
      где n₁, n₂... — количества одинаковых элементов

🔢 ПРЕОБРАЗОВАНИЯ СИСТЕМ СЧИСЛЕНИЯ

41. Из двоичной в десятичную

    int('1011', 2)  # = 11
    # Или вручную: 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 8+0+2+1=11
    

42. Из десятичной в двоичную

    bin(n)[2:]  # строка
    # Или: format(n, 'b')
    

43. Из десятичной в любую систему (2-36)

    def to_base(n, base):
        digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        if n == 0: return "0"
        result = ""
        while n > 0:
            result = digits[n % base] + result
            n //= base
        return result
    

44. Шестнадцатеричная система

    hex(n)[2:]  # строка
    int('FF', 16)  # = 255
    

🔢 ФОРМУЛЫ ДЛЯ ОПТИМИЗАЦИИ

45. Сумма арифметической прогрессии через среднее
    sum = среднее × количество
    Среднее = (первый + последний) / 2

46. Быстрое возведение в степень

    def pow_mod(a, b, mod=None):
        result = 1
        while b > 0:
            if b & 1:
                result = result * a
                if mod: result %= mod
            a = a * a
            if mod: a %= mod
            b >>= 1
        return result
    

47. Обратный элемент по модулю (для простого p)
    a^(-1) ≡ a^(p-2) (mod p) (малая теорема Ферма)
    Только если p — простое и a не делится на p

48. Формула для суммы цифр

    def sum_digits(n):
        s = 0
        while n:
            s += n % 10
            n //= 10
        return s
    

49. Проверка на простое число

    def is_prime(n):
        if n < 2: return False
        if n % 2 == 0: return n == 2
        if n % 3 == 0: return n == 3
        i = 5
        while i * i <= n:
            if n % i == 0 or n % (i + 2) == 0:
                return False
            i += 6
        return True
    

🔢 ПОЛЕЗНЫЕ МАТЕМАТИЧЕСКИЕ СВОЙСТВА

50. Среднее арифметическое ≥ среднее геометрическое
    (a+b)/2 ≥ √(ab) для неотрицательных a,b

51. Числа Фибоначчи

    • Формула Бине: F_n ≈ φⁿ/√5, где φ=(1+√5)/2
    • Свойство: F_{n+m} = F_{n-1}F_m + F_n F_{m+1}
    • Быстрое вычисление через матрицы

52. Факториал
    n! = 1×2×...×n
    Приближение Стирлинга: n! ≈ √(2πn)(n/e)ⁿ

53. Логарифмические тождества

    • log(a×b) = log(a) + log(b)
    • log(aᵇ) = b×log(a)
    • logₐb = log_c b / log_c a (смена основания)

🎯 КАК ИСПОЛЬЗОВАТЬ НА СОБЕСЕДОВАНИИ

1. Распознавайте паттерны:

   • "Сумма всех подмассивов" → n*(n+1)//2
   • "Количество пар" → n*(n-1)//2
   • "Поворот изображения" → формулы транспонирования

2. Оптимизируйте с помощью битов:

   • Задача с 26 буквами → битовая маска (int32 хватит)
   • Проверка уникальности → быстро через биты

3. Используйте математические свойства:

   • Делимость на 3/9 → сумма цифр
   • Степень двойки → n & (n-1) == 0

4. Работа с координатами:

   • Манхэттенское расстояние → |dx|+|dy|
   • Коллинеарность точек → векторное произведение

Запомните: Главное — не выучить все формулы наизусть, а понимать, когда какую применять. На собеседовании можно вывести многие формулы, но знание ключевых ускоряет решение в разы.