Арифметика
НОК: наименьшее общее кратное
LCD мониторы 60, 120, 144 Гц - частота синхронного кадра = LCM. Планировщик задач OS вычисляет LCM периодов. Сложение дробей требует LCM знаменателей. Одна формула - везде.
- OS планировщик: гиперпериод расписания = LCM периодов задач (RMS/EDF алгоритмы реального времени)
- Python fractions.Fraction: автоматически находит LCM знаменателей при сложении
- Аппаратная синхронизация: HDMI/DisplayPort sync pulses используют LCM частот дисплеев
НОК: наименьшее общее кратное
LCD-мониторы обновляются с частотой 60, 120 или 144 Гц. Если подключить два дисплея с разными частотами к одной видеокарте, момент синхронного обновления (когда оба дисплея одновременно начинают новый кадр) наступит через LCM(f₁, f₂) миллисекунд. Для 60 и 144 Гц: LCM(60, 144) = 720 мс.
**Наименьшее общее кратное** lcm(a, b) - наименьшее натуральное число, кратное одновременно обоим a и b.
lcm(4, 6): кратные 4: {4,8,12,16,...}, кратные 6: {6,12,18,...}. Первое пересечение: 12. Ответ: lcm(4,6) = 12.
Связь НОК и НОД через разложение на простые: gcd берёт общие простые в минимальных степенях, lcm - в максимальных. Например, 12 = 2²*3 и 18 = 2*3²: gcd = 2^min(2,1) * 3^min(1,2) = 2*3 = 6; lcm = 2^max(2,1) * 3^max(1,2) = 4*9 = 36.
lcm(8, 12) = ?
Формула lcm = ab/gcd: эффективное вычисление
Прямой поиск lcm может быть медленным для больших чисел. Ключевое соотношение через НОД:
Это следует из того, что gcd * lcm = a * b (каждый простой в степени min + max = сумма = sum, а сумма степеней в a*b = e_a + e_b = min + max для каждого простого).
В коде: `a // gcd(a,b) * b` вместо `a * b // gcd(a,b)` - важный порядок! Первый вариант предотвращает целочисленное переполнение: делим до умножения. Для 32-битных a, b произведение a*b может переполниться.
Почему lcm(a,b) = a*b/gcd(a,b)?
НОК в планировании, дробях и синхронизации
НОК решает задачу **синхронизации периодических событий**: когда несколько процессов с разными периодами совпадут. Планировщик задач в OS, синхронизация кадров, циклические задания в cron.
Сложение дробей: 1/a + 1/b = (b + a) / lcm(a,b) * gcd(a,b) - нужен общий знаменатель. Python's `Fraction` использует lcm автоматически. В компиляторах: выравнивание данных в памяти - lcm размеров типов.
В OS планировщик использует lcm периодов задач для вычисления гиперпериода (hyperperiod) - минимального окна, в котором повторяется весь расписание. Для задач с периодами {2, 3, 5} мс: гиперпериод = lcm(2,3,5) = 30 мс. За 30 мс: 15 + 10 + 6 = 31 активация.
Общий знаменатель для сложения 1/6 + 1/10 (наименьший):
Ключевые идеи
- lcm(a,b) = наименьшее n: a | n и b | n
- lcm(a,b) = a * b / gcd(a,b) - через Евклида, эффективно
- gcd * lcm = a * b (min + max степеней = sum для каждого простого)
- lcm нескольких: lcm(a,b,c) = lcm(lcm(a,b), c) - ассоциативно
- Применения: синхронизация периодов, общий знаменатель, выравнивание памяти
Связанные темы
НОК и НОД - пара взаимодополняющих операций:
- НОД — lcm(a,b) = a*b / gcd(a,b) - lcm сводится к НОД через Евклида
- Разложение на множители — lcm через разложения: max степеней каждого простого; gcd через разложения: min степеней