Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел. Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД. Алгоритм Евклида делением Пример: Найти НОД для 30 и 18. 30 / 18 = 1 (остаток 12) 18 / 12 = 1 (остаток 6) 12 / 6 = 2 (остаток 0) Конец: НОД – это делитель 6...

Любая сложная задача всегда может быть разбита на несколько простых задач. Те в свою очередь могут быть разбиты на ещё1 более мелкие задачи. В олимпиадных задачах по программированию очень часто требуется найти НОД(наибольший общий делитель) или НОК(наименьшее общее кратное) двух или более чисел. Это может быть задача по фасовке предметам по ящикам (целочисленное деление) или формирование людей в бригады. Короче там где нужно искать целые числа после деления. Пример двух чисел 6 и 15. Очевидно, что НОД (наибольшим общим делителем) будет число 3...