Разложим число 216 на простые множители. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
216 : 2 = 108 - делится на простое число 2
108 : 2 = 54 - делится на простое число 2
54 : 2 = 27 - делится на простое число 2
27 : 3 = 9 - делится на простое число 3
9 : 3 = 3 - делится на простое число 3.
Разложим число 336 на простые множители. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
336 : 2 = 168 - делится на простое число 2
168 : 2 = 84 - делится на простое число 2
84 : 2 = 42 - делится на простое число 2
42 : 2 = 21 - делится на простое число 2
21 : 3 = 7 - делится на простое число 3.
Выделим выпишем общие множители
216 = 2 ⋅ 2 ⋅ 2 ⋅ 3 ⋅ 3 ⋅ 3
336 = 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 3 ⋅ 7
Общие множители (216 ; 336) : 2, 2, 2, 3
Теперь, чтобы найти НОД нужно перемножить общие множители
Если сотрудников 102, то может выйти так, что у 101 сотрудника зарплата 1 тугрик, а у оставшегося - все остальные тугрики. В таком случае зарплату раздать не выйдет, так как есть только 100 монет по 1 тугрику.
Пусть сотрудников 101 или меньше. Упорядочим их по убыванию оставшегося размера выплаты. Будем распределять монеты так: Заплатим первому в очереди 1 монетой максимального номинала из имеющихся, а затем поставим его в очередь согласно оставшемуся размеру выплаты.
Почему это сработает: если максимальный номинал монеты x >= 3, то осталось выплатить не меньше, чем 100*(1+2+3+...+(x-1))+x = 50x^2-49x, у первого в очереди остаток к выплате не меньше, чем (50x^2-49x)/101 >= x. Если x = 2, то первому в очереди надо выплатить не меньше 2 тугриков, поскольку в противном случае сумма всех монет была бы не больше 101 (не более 101 человека, каждому надо выплатить не более 1 тугрика), но сумма всех монет не меньше, чем 100*1 + 2 = 102. Если x = 1, то очевидно, выплатить получится.
НОД (216 ; 336) = 2 ∙ 2 ∙ 2 ∙ 3 = 24
Пошаговое объяснение:
Разложим число 216 на простые множители. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
216 : 2 = 108 - делится на простое число 2
108 : 2 = 54 - делится на простое число 2
54 : 2 = 27 - делится на простое число 2
27 : 3 = 9 - делится на простое число 3
9 : 3 = 3 - делится на простое число 3.
Разложим число 336 на простые множители. Начинаем подбирать делитель из простых чисел, начиная с самого маленького простого числа 2, до тех пор, пока частное не окажется простым числом
336 : 2 = 168 - делится на простое число 2
168 : 2 = 84 - делится на простое число 2
84 : 2 = 42 - делится на простое число 2
42 : 2 = 21 - делится на простое число 2
21 : 3 = 7 - делится на простое число 3.
Выделим выпишем общие множители
216 = 2 ⋅ 2 ⋅ 2 ⋅ 3 ⋅ 3 ⋅ 3
336 = 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 3 ⋅ 7
Общие множители (216 ; 336) : 2, 2, 2, 3
Теперь, чтобы найти НОД нужно перемножить общие множители
ответ: НОД (216 ; 336) = 2 ∙ 2 ∙ 2 ∙ 3 = 24