题目意思：

给你1 - n的一个序列，你可以随便定义一个长度形成环，过了一段时间会回到1 - n这个状态，问这个时间的集合大小是多少？

Solution

显然这个回到起点的时间就是LCM全部环的长度，问题就变成了，n分隔成若干个数，求他们LCM的种类数。
枚举全部的可能一定会T掉，所以转换一下，LCM的种类数，也就是LCM不变的情况算一次即可，当你又枚举了不是一个不是素因子的数，一定会和之后的枚举重复，所以这类枚举是不必要的

使用筛法选出全部的素数，使用dp[i][j]代表前i个素因子总和为j的情况，
那么可以得到转移方程
观察这个式子，和完全背包问题是原模原样的，使用滚动数组 or 直接压掉第一维节约空间，最终合计dp[n][0~n]就是方案数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 7;

int cnt;
bool vis[N];
vector<int> prime;

void getprime() {
    memset(vis, true, sizeof vis);
    for (int i = 2; i < N; ++i) {
        if (vis[i])    prime.push_back(i), ++cnt;
        for (int j = 0; j < cnt; ++j) {
            if (i * prime[j] >= N)    break;
            vis[i * prime[j]] = 0;
            if (i % prime[j] == 0)    break;
        }
    }
}

ll dp[N], ans;

int main() {
    getprime();
    int n;
    scanf("%d", &n);
    dp[0] = 1;
    for (int i = 0; i < cnt; ++i) {
        for (int j = n; j >= prime[i]; --j)
            for (int k = prime[i]; k <= j; k *= prime[i])
                dp[j] += dp[j - k];
    }
    for (int i = 0; i <= n; ++i)
        ans += dp[i];
    printf("%lld\n", ans);
    return 0;
}