Конспект № 17. Тема: «Наименьшее общее кратное (НОК)»
Общим кратным нескольких чисел называется число, которое является кратным для каждого из них. Пример: Числа 2 и 3 имеют общее кратное 6, так как 6 делится без остатка и на 2 и на 3. Число 24 также общее кратное чисел 2 и 3 (24÷2=12, 24÷3=8). Среди всех общих кратных всегда есть наименьшее. Наименьшим общим кратным нескольких данных чисел называется самое меньшее число, которое делится на каждое из этих чисел. Для краткой записи наименьшего общего кратного используют аббревиатуру НОК. Для двух чисел...
1149 читали · 2 года назад
Легко находим НОК или НОД с помощью алгоритма Евклида
Любая сложная задача всегда может быть разбита на несколько простых задач. Те в свою очередь могут быть разбиты на ещё1 более мелкие задачи. В олимпиадных задачах по программированию очень часто требуется найти НОД(наибольший общий делитель) или НОК(наименьшее общее кратное) двух или более чисел. Это может быть задача по фасовке предметам по ящикам (целочисленное деление) или формирование людей в бригады. Короче там где нужно искать целые числа после деления. Пример двух чисел 6 и 15. Очевидно, что НОД (наибольшим общим делителем) будет число 3...