Соответствия, сравнения, количества

Рассмотрим произвольное -элементное подмножество. Назовём сдвигом множества прибавление к каждому элементу. Будем двигать рассматриваемое подмножество до тех пор, пока не сдвинем его раз. Мы получили подмножеств из элемента. Во-первых, эти множества имеют различные суммы по модулю Предположим противное, пусть у множество была сумма его сдвинули раз и получили такой же остаток при делении на В таком случае то есть кртано но это невозможно, потому что и взаимнопросты, а — число от до Следовательно, среди этих подмножеств сумма элементов делится на только в одном.

Таким образом, -элементые подмножества разбиваются на группы по подмножеств, в каждой из которых только у одного сумма элементов делится на Значит, ответом будет — количество -элементных подмножеств, поделённое на