pro.algorithms
У вас есть числа s и n . Найдите такие n
натуральных чисел, сумма которых равна s
и значение НОД этих чисел максимально.
Найдите это максимальное значение НОД чисел.
Какой подход можно использовать ?
2 ответов
Пусть ответ - нод чисел, равен k Тогда все слагаемые делятся на k, их сумма - s, тоже делится на k Также их сумма >= n*k Следовательно, ответ это какой то делитель s, который меньше или равен s/n Несложно понять, что ответ это наибольший делитель s, который <= s/n Перебрать все делители можно за sqrt(s)
.
Azmiddin
Автор вопроса
Пусть ответ - нод чисел, равен k Тогда все слагаем...
Большое спасибо понятно. Теперь надо написать все это в одну строчку странное олимпиада
Похожие вопросы
Обсуждают сегодня