(Analysis by Benjamin Qi)

Call the number of steps that a permutation takes the period of the permutation. Every permutation can be partitioned into cycles of sizes $c_1,c_2,c_3,\ldots,c_k$ such that $c_1+c_2+\ldots+c_k=N$ (see Swapity Swapity Swap from the last contest). Then the period is equal to $\text{lcm}(c_1,c_2,\ldots,c_k)$.

Suppose that we want find the minimum $n$ such that there exists a permutation of length $n$ with period $K=\prod p_i^{e_i},$ where the right side denotes the prime factorization of $K$. It turns out that $n=\sum p_i^{e_i}$ because

• It is never optimal to have $\text{gcd}(c_i,c_j)>1$ for $i\neq j$ because then we could divide each of $c_i,c_j$ by an appropriate factor. This would reduce the value of $\sum_{i=1}^kc_i$.
• It is never optimal to have $c_i=pq$ for $\min(p,q)>1$ and $\text{gcd}(p,q)=1$ because then $p+q<c_i$.

Thus, we need to find the sum of all positive integers $K$ such that $\sum p_i^{e_i}\le N$.

Subtask $N\le 100$:

Just searching for all possible $K$ suffices (there are only $18663$ for $N=100$). However, this number grows quite rapidly as $N$ increases.

Full Credit:

Maintain a DP table storing the sum of all possible $K$ for each prime power sum $n$ in $[0,N]$. Then we can add prime powers in increasing order of $p$ and update the table in $O(N)$ for each of them.

Unfortunately, I was unaware that the sequence could be found on OEIS. I'll try to be more careful about this in the future ...

Mark Chen's code:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXP = 1234;
const int MAXN = 10005;

LL res[MAXP][MAXN];  // result for permutations of length n restricted to using the first p primes

int n; LL m;

LL mul(LL x, LL y) {
return (x * y) % m;
}

LL add(LL x, LL y) {
x += y;
if (x >= m) x -= m;
return x;
}

LL sub(LL x, LL y) {
x -= y;
if (x < 0) x += m;
return x;
}

int main() {
freopen("exercise.in","r",stdin);
freopen("exercise.out","w",stdout);
cin >> n >> m;

vector<int> composite(n+1);
vector<int> primes;

for (int i = 2; i <= n; i++) {
if (!composite[i]) {
primes.push_back(i);
for (int j = 2*i; j <= n; j += i) {
composite[j] = 1;
}
}
}

if (primes.size() == 0) {
cout << "1\n";
return 0;
}

for (int j = 0; j <= n; j++) res[j] = 1;  // identities

for (int i = 1; i <= primes.size(); i++) {
for (int j = 0; j <= n; j++) {
res[i][j] = res[i-1][j];

int pp = primes[i-1];
while (pp <= j) {