Task 100. Овощная нарезка
UniLecsЗадача: вам даны N нарезанных колечек овощей: помидора (П) и огурца (О) разложенных на тарелке. В помидорах и огурцах вы не ограничены, поэтому любое нарезанное колечко может быть как огурцом так и помидором. Вам необходимо посчитать кол-во различных вариантов нарезок разложенных на тарелке. При сравнении тарелку можно поворачивать по кругу.
Входные данные: N - кол-во нарезанных колечек, где N больше 0 и меньше 100000
Вывод: кол-во различных вариантов нарезок разложенных на тарелке.
Пример: N = 3
Answer = 4.
Идея: для начала поясним, что значит условие про возможность поворачивать тарелку по кругу для сравнения нарезок. Это значит, что, например, нарезки для 3х колечек вида:
- Помидор - Помидор - Огурец,
- Помидор - Огурец - Помидор,
- Огурец - Помидор - Помидор
будут одинаковыми.
Дальше воспользуемся теоремой Пойа, ктр можем рассмотреть на класс.задаче из комбинаторики: необходимо посчитать кол-во различных N бусинок, каждая из ктр может быть покрашена в один из K цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).
Здесь мы опустим все выкладки теоремы Пойа. Все выкладки и док-во теоремы Пойа вы можете посмотреть тут:
В конечном итоге, для решения такого класса задач мы можем использовать след.формулу:
Можно оставить формулу в таком виде, а можно её свернуть ещё больше. Перейдём от суммы по всем i к сумме только по делителям n. Действительно, в нашей сумме будет много одинаковых слагаемых: если i не является делителем, то таковой делитель найдётся после вычисления gcd(i,n). Следовательно, для каждого делителя d|n его слагаемое слагаемое k^d (где d = gcd(i,n)) учтётся несколько раз, т.е. сумму можно представить в таком виде:
где Сd - это кол-во таких чисел i, что gcd(i,n)=d.
Окончательно эту формулу можно представить через функцию Эйлера:
Реализация:
https://gist.github.com/unilecs/f875eb158af2d38b63e00f6947c1825d
Test: