Где применяется
1. Задача
Видео шириной 1920 и высотой 1080. Человек называет такой формат 16:9. Чтобы получить эту запись, оба числа делят на самое большое число, на которое они оба делятся нацело. Для 1920 и 1080 это 120: 1920 / 120 = 16, 1080 / 120 = 9.
Как найти это число? Медленный способ: перебирать кандидатов от меньшего числа вниз и проверять, делит ли кандидат оба числа. Для маленьких чисел это быстро. Для пары 1000000007 : 500000000 пришлось бы проверить до 500 миллионов кандидатов.
Похожий вопрос возникает, когда два повторяющихся события должны совпасть. Одна задача запускается каждые 4 секунды, другая каждые 6. Через сколько секунд они сработают одновременно? Здесь нужно обратное: самое маленькое число, которое делится на оба. Для 4 и 6 это 12.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитsieve(30)| 1 | 2 | 3 | 4 | 5 | 6 |
| 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 |
| 19 | 20 | 21 | 22 | 23 | 24 |
| 25 | 26 | 27 | 28 | 29 | 30 |
Ищем все простые числа до 30. Сначала все числа от 2 на месте; после вычёркивания кратных останутся только простые.
Столбики: по одному на каждое число от 2 до 49. Сначала все подняты; составное число падает в ноль, простые остаются стоять.
Одна операция: одно деление или одно вычёркивание. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n√n)O(n log log n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- сократить дробь до несократимого вида
- перечислить все простые числа до n
- ответ по модулю 1e9+7
- когда снова совпадут два повторяющихся интервала (НОК)
Похоже, но не то
- Битовые манипуляции (Bit manipulation)
Оба работают с самим числом. Та страница про отдельные биты.
- Хеш-множество / словарь (Hash set / map)
Множество простых чисел всё равно надо как-то построить. Решето и есть способ его построить.
- Динамическое программирование (1-D) (Dynamic programming (1-D))
Формула отвечает сразу там, где динамика заполняет таблицу. Сначала поищите замкнутую форму.
- Префиксные суммы (Prefix sums)
Префиксные суммы отвечают по сохранённым значениям. Здесь ответ следует из свойств самих чисел.
НОД стоит O(log от меньшего значения). Решето до 1e7 нормально, а до 1e9 уже нет.
На LeetCode
Задачи, где числа или строки сводят к общему шагу, например НОД массива, наклоны между точками или то, что можно отмерить двумя кувшинами. Цикл Евклида находит НОД за O(log n), а НОК получается из него.
Возьми наименьшее и наибольшее число и верни gcd из урока для этих двух.
Общая строка-делитель есть, только если str1 + str2 равно str2 + str1, и тогда её длина это gcd двух длин.
Посчитай каждое значение карт и проверь, что gcd всех счётчиков не меньше 2.
Двумя кувшинами можно отмерить ровно кратные их gcd, но не больше их общего объёма.
Храни каждый наклон от точки как пару, сокращённую на gcd, с одним правилом знака, и равные наклоны дадут равные ключи в Map.