对于一个排列Ａ，他的需要的次数
$x$ = $lcm(a_1, a_2, a_3, a_4, ..., a_m)$
其中m为这个排列置换的个数，$a_1$,$a_2$,$a_3$...为每个置换的大小， 至于为什么是这样，　应该比较容易理解吧。　
举个栗子:
$n=5$ $A$ = {$3,1,2,5,4$}
那么它的两个置换分别为{$3,1,2$}, {$5,4$}； 对于第一个置换每三次会还原一次，　对于第二个置换每两次会还原一次，　那么这个排列对应的次数就应该是lcm(2,3) = 6;
所以现在题目可以转化成，
有多少不同的$sum$, 选若干个数，使它们的$lcm = sum$, 且和$<n$；

那么对于一个$sum$，我们只需要找到使lcm等于它的最小的和，　如果这个值$\leq n$, $sum$ 就是$OK$的。　这个最小的和是比较好求的 对$sum$质因数分解：　sum = $p_1^{a_1} * p_2^{a_2}...*p_m^{a_m}$，　最小和即为 $p_1^{a_1}+p_2^{a_2}+...+p_m^{a_m}$, 这个应该是比较显然的。 那么我们对每一个质数分别考虑贡献就行了，　具体的dp细节可以参考代码，十分好写

#include<bits/stdc++.h>
#define int long long
#define reg register
#define maxn 300001
using namespace std;
int n, mod, prime[maxn], not_prime[maxn], cnt, f[maxn],  g[maxn], ans;
signed main(){
   // freopen("exercise.in", "r", stdin);
   // freopen("exercise.out", "w", stdout);
    cin >> n;
    for(int i = 2; i <= n; i++){
        if(!not_prime[i]) prime[++cnt] = i;
        for(int j = 1; j <= cnt && prime[j] * i <= n; j++){
            not_prime[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
    f[0] = 1;
    for(int i = 1; i <= cnt; i++){
        for(int j = prime[i]; j <= n; j = j * prime[i])
            for(int k = j; k <= n; k++) g[k] += f[k - j];  
        for(int j = 0; j <= n; j++) f[j] += g[j], g[j] = 0;
    }
    for(int i = 0; i <= n; i++) ans += f[i];
    cout << ans << endl; return 0;
}

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1010;
LL dp[N];
bool v[N];
int prime[N], pr;

void init() {
	pr = 0; memset(v, 0, sizeof(v));
	for (int i = 2; i <= N - 10; i ++) {
		if (!v[i]) {
			pr ++;
			prime[pr] = i;
		}
		for (int j = 1; j <= pr && i * prime[j] <= N - 10; j ++) {
			int pj = prime[j];
			v[i * pj] = 1;
			if (i % pj == 0) {
				break;
			}
		}
	}
}

LL calc(int n) {
	memset(dp, 0, sizeof(dp));
	dp[0] = 1;
	for (int i = 1; i <= pr && prime[i] <= n; i ++) {
		int pi = prime[i];
		for (int j = n; j >= pi; j--) {
			for (int k = pi; k <= j; k *= pi) {
				dp[j] += dp[j - k]; 
			}
		}
	}
	return dp[n];
}

LL f[N];

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	init();
		
	f[1] = 1;
	for (int i = 2; i <= 1000; i ++) {
		f[i] = f[i - 1] + calc(i);
	}
	
	int n;
	cin >> n;
	cout << f[n] << "\n";
	
	return 0;
}