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

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

Правило Евклида заменяет пару чисел меньшей парой. НОД чисел 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;
}

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

Посчитать простые числа меньше 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
• •когда снова совпадут два повторяющихся интервала (НОК)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

varies

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