#PU1043. USACO 2020 US Open Contest, Gold — Problem 3. Exercise
USACO 2020 US Open Contest, Gold — Problem 3. Exercise
USACO 2020 US Open Contest, Gold — Problem 3. Exercise
题目描述
Farmer John has come up with a new morning exercise routine for the cows (again)! As before, Farmer John's cows () are standing in a line. The -th cow from the left has label for each . He tells them to repeat the following step until the cows are in the same order as when they started. Given a permutation of length , the cows change their order such that the -th cow from the left before the change is -th from the left after the change. For example, if then the cows perform one step. If , then the cows perform six steps. The order of the cows from left to right after each step is as follows: 0 steps: 1 step: 2 steps: 3 steps: 4 steps: 5 steps: 6 steps: Find the sum of all positive integers such that there exists a permutation of length that requires the cows to take exactly steps. As this number may be very large, output the answer modulo (, is prime).
输入格式
The first line contains and .
输出格式
A single integer.
数据范围
Test cases 2-5 satisfy . Test cases 6-10 satisfy no additional constraints. Problem credits: Benjamin Qi
样例
样例 1
5 1000000007
21
There exist permutations that cause the cows to take $1$, $2$, $3$, $4$, $5$,
and $6$ steps. Thus, the answer is $1+2+3+4+5+6=21$.