Спортивное программирование

👨‍💻 Сегодня разберём задачу «Максимальный НОД». В ней нужно построить строго возрастающую последовательность a[1], a[2], ..., a[k] из k натуральных чисел так, чтобы их сумма была равна n, а наибольший общий делитель был максимален среди всех возможных вариантов. Пусть НОД всех чисел a[1], a[2], ..., a[k] равен g. Тогда каждое число можно представить в виде a[i] = g × b[i], где b[i] — натуральное число. Если вынести g за скобки, получим g × (b[1] + b[2] + ... + b[k]) = n. Отсюда следует, что g должен быть делителем числа n. Значит, можно перебрать все делители n и для каждого проверить, сможем ли мы построить подходящую строго возрастающую последовательность b[1], b[2], ..., b[k]. Минимальная сумма k различных натуральных чисел достигается на последовательности 1, 2, ..., k, поэтому условие существования такое: k × (k + 1) / 2 ≤ n / g. Если это условие выполняется, выгоднее всего взять числа 1, 2, ..., k − 1, а весь оставшийся остаток добавить к последнему числу. При этом последовательность останется строго возрастающей. Значит, нам нужно найти максимальный делитель g числа n, для которого выполняется это условие, а затем восстановить ответ. В задаче есть ловушка ❣️: при k = 10^10 выражение k × (k + 1) / 2 уже переполняет 64-битный целочисленный тип, поэтому для сравнения в этой задаче удобно считать его в типе long double, ведь нам важны лишь порядок и лидирующие биты. исходный код решения на C++