Математика и теория чисел (НОД, решето, модульная арифметика)

Математика и теория чисел (НОД, решето, модульная арифметика): как это работает?

Правило Евклида заменяет пару чисел меньшей парой. НОД чисел a и b равен НОД чисел b и a по модулю b.

Цикл Евклида останавливается, когда второе число стало нулём. Оставшееся число и есть ответ.

Наименьшее общее кратное следует из НОД. Это a умножить на b и поделить на их НОД.

Решето вычёркивает кратные каждого встреченного простого. Всё невычеркнутое является простым.

Модульная арифметика держит числа маленькими. Берите остаток после каждого шага, а не только в конце.

У деления простой модульной формы нет. Вместо него нужен обратный элемент по модулю.

Источники: Википедия: Алгоритм Евклида, Википедия: Решето Эратосфена

1. нод(48, 18)48 по модулю 18 даёт 12.
2. нод(18, 12)18 по модулю 12 даёт 6.
3. нод(12, 6)12 по модулю 6 не даёт ничего.
4. нод(6, 0) = 6Второе число стало нулём. Ответ равен 6.
5. нок = 48 на 18 делить на 6Получается 144, и ни одно кратное не перечислялось.

function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}
function lcm(a, b) {
    return (a / gcd(a, b)) * b;
}

function gcd(a: number, b: number): number {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}
function lcm(a: number, b: number): number {
    return (a / gcd(a, b)) * b;
}

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b

function gcdEuclid(int $a, int $b): int {
    while ($b !== 0) {
        [$a, $b] = [$b, $a % $b];
    }
    return $a;
}
function lcm(int $a, int $b): int {
    return intdiv($a, gcdEuclid($a, $b)) * $b;
}

    public static int gcd(int a, int b) {
        while (b != 0) {
            int rest = a % b;
            a = b;
            b = rest;
        }
        return a;
    }

    public static long lcm(int a, int b) {
        return (long) (a / gcd(a, b)) * b; // divide first: the product can overflow
    }

    public static int Gcd(int a, int b) {
        while (b != 0) {
            int rest = a % b;
            a = b;
            b = rest;
        }
        return a;
    }

    public static long Lcm(int a, int b) {
        return (long) (a / Gcd(a, b)) * b; // divide first: the product can overflow
    }

Математика и теория чисел (НОД, решето, модульная арифметика): разбор примера

Посчитать простые числа меньше n

Посчитайте простые числа строго меньше n.

Проверять каждое число по отдельности слишком медленно при большом n.

Вычёркивайте все кратные каждого простого как составные.

Начинайте вычёркивать с квадрата простого. У всего меньшего уже есть меньший делитель.

function countPrimes(n) {
    if (n < 3) return 0;

    const composite = new Array(n).fill(false);
    let count = 0;

    for (let p = 2; p < n; p++) {
        if (composite[p]) continue;
        count++;

        // start at p * p: everything smaller already has a smaller factor
        for (let multiple = p * p; multiple < n; multiple += p) {
            composite[multiple] = true;
        }
    }

    return count;
}

Математика и теория чисел (НОД, решето, модульная арифметика): когда применять?

Паттерн «Математика и теория чисел (НОД, решето, модульная арифметика)» нужен, когда в условии есть слова «сократить дробь до несократимого вида», «перечислить все простые числа до n» или «ответ по модулю 1e9+7».

• •сократить дробь до несократимого вида
• •перечислить все простые числа до n
• •ответ по модулю 1e9+7
• •когда снова совпадут два повторяющихся интервала (НОК)

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

Математика и теория чисел (НОД, решето, модульная арифметика): с чем путают?

Паттерн «Математика и теория чисел (НОД, решето, модульная арифметика)» чаще всего путают с этими паттернами: Битовые манипуляции, Хеш-множество / словарь, Динамическое программирование (1-D) и Префиксные суммы.

• Битовые манипуляции (Bit manipulation): Оба работают с самим числом. Та страница про отдельные биты.
• Хеш-множество / словарь (Hash set / map): Множество простых чисел всё равно надо как-то построить. Решето и есть способ его построить.
• Динамическое программирование (1-D) (Dynamic programming (1-D)): Формула отвечает сразу там, где динамика заполняет таблицу. Сначала поищите замкнутую форму.
• Префиксные суммы (Prefix sums): Префиксные суммы отвечают по сохранённым значениям. Здесь ответ следует из свойств самих чисел.

Математика и теория чисел (НОД, решето, модульная арифметика): частые ошибки

• Берут остаток только в конце

  Значение переполнится задолго до этого. Уменьшайте его после каждого умножения.

• Получают отрицательный остаток

  В JavaScript минус один по модулю пять равен минус одному. Добавьте модуль и возьмите остаток снова.

• Начинают внутренний цикл решета с удвоенного простого

  У всего ниже квадрата простого уже есть меньший делитель. Такой старт тратит большую часть работы.

• Проверяют делители дальше квадратного корня

  Делитель выше корня всегда идёт в паре с делителем ниже. Останавливайтесь на корне.

Математика и теория чисел (НОД, решето, модульная арифметика): задачи с собеседований

Паттерн «Математика и теория чисел (НОД, решето, модульная арифметика)» решает такие задачи с собеседований: Наибольший общий делитель строк, Подсчёт простых чисел, Уродливые числа II, Степень тройки, Дробь в периодическую десятичную, Номер колонки в таблице и Счастливое число.

• Наибольший общий делитель строк: Длина ответа это НОД двух длин.
• Подсчёт простых чисел: Решето вместо проверки каждого числа.
• Уродливые числа II: Три указателя по кратным 2, 3 и 5.
• Степень тройки: Повторное деление или одна проверка делимости.
• Дробь в периодическую десятичную: Повторившийся остаток и отмечает период.
• Номер колонки в таблице: Система по основанию 26, но без нулевой цифры.
• Счастливое число: Поиск цикла по суммам квадратов цифр.

Математика и теория чисел (НОД, решето, модульная арифметика): сложность по времени и памяти

varies

НОД стоит O(log от меньшего значения). Решето до 1e7 нормально, а до 1e9 уже нет.